[코드트리] 정수 사각형 최솟값의 최대

문제링크

문제

n * n의 숫자 행렬이 있을때, 오른쪽, 아래로만 이동할 수 있는데
(1, 1)에서 (n, n)까지의 경로에서의 최소값의 최대값을 구하라

문제 풀이

• DP인 것은 알 것 같음.
• DP로 그냥 경로의 최소 값은 쉽게 구할 수 있음
• 최소값의 최대값은 어떻게 구하는가 -> 핵심

문제 해결 방법

		int[][] dp = new int[n][n];
        dp[0][0] = matrix[0][0];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                int fromTop = (i > 0) ? Math.min(dp[i - 1][j], matrix[i][j]) : Integer.MIN_VALUE;
                int fromLeft = (j > 0) ? Math.min(dp[i][j - 1], matrix[i][j]) : Integer.MIN_VALUE;

                dp[i][j] = Math.max(fromTop, fromLeft);
            }
        }
        System.out.println(dp[n - 1][n - 1]);

• 아래, 오른쪽 두방향으로만 진행 가능하므로, 두가지 방법으로 진행 했을때,
  그 길의 최소 값 중 최대를 구하면 최소값의 최대값을 구할 수 있다.