[DP/자바] 코드트리 IL. 정수 사각형 최댓값의 최소

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 분석

인접한 항으로 이동하는게 아니라 모든 항을 대상으로 움직이는 패턴이 정해져 있고 , n 번째 위치의 숫자가 무엇일지 알아보는 문제이므로 전형적인 DP 문제이다. 하지만 이 문제에 대한 점화식을 세우는 것이 개인적으로는 어려웠는데, 최댓값을 최소로 하는 프로그램이므로, "각 패턴의 최대값끼리의 최솟값을 구하면 된다"라는 것을 감안하여 세우니 되었다. 감 잡기 전에는 와닿지 않는 말이었는데, 식을 세우고 나니 사실 문제가 매우 명확하게 제시되어있는 것 같다는 생각도 했다.

 

문제 풀이

package 코드트리.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.List;

public class 정수_사각형_최댓값의_최소 {
    private static int n;
    private static int[][] arr;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = Math.max(arr[0][i], dp[0][i - 1]);
            dp[i][0] = Math.max(arr[i][0], dp[i - 1][0]);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(Math.max(arr[i][j], dp[i - 1][j]), Math.max(arr[i][j], dp[i][j - 1]));
            }
        }
        System.out.println(dp[n - 1][n - 1]);

    }
}