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

📖 문제

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

 

 

 

💡  풀이 방식

• DP

1. 2차원 배열을 입력받는다.

2. 2차원 배열 dp를 초기화한다.

    - dp[0][0] = arr[0][0]

    - 맨 위쪽 행은 arr 배열의 왼쪽 칸과 현재 칸의 값 中 작은 값으로 초기화

    - 맨 왼쪽 열은 arr 배열의 위쪽 칸과 현재 칸의 값 中 작은 값으로 초기화

 

3. 나머지 칸은 현재 칸의 위쪽과 왼쪽 中 더 큰 값을 구한다.

그리고 이 값과 현재 칸의 값을 비교해 둘 中 더 작은 값으로 현재 칸의 값을 갱신한다.

dp[i][j] = Math.min(Math.max(dp[i - 1][j], dp[i][j - 1]), arr[i][j]);

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] arr, dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
 
        arr = 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 = new int[N][N];
 
        // dp 배열 초기화
        dp[0][0] = arr[0][0];
 
        for(int i = 1 ; i < N ; i++) {
            dp[i][0] = Math.min(dp[i - 1][0], arr[i][0]);   // 맨 위쪽 행
            dp[0][i] = Math.min(dp[0][i - 1], arr[0][i]);   // 맨 왼쪽 열
        }
 
        // 탐색하는 위치의 위쪽 값과 왼쪽 값 중 큰 값과
        // 해당 위치의 숫자 중 최솟값을 구한다.
        for(int i = 1 ; i < N ; i++) {
            for(int j = 1 ; j < N ; j++) {
                dp[i][j] = Math.min(Math.max(dp[i - 1][j], dp[i][j - 1]), arr[i][j]);
            }
        }
 
        System.out.println(dp[N - 1][N - 1]);
    }
}

 

 

 

---

💦 어려웠던 점

점화식을 찾지 못 해 헤맸다.

"적혀있는 숫자들 중 최솟값을 최대로" 이 말을 이해하지 못 하고 헤매다 다른 분 풀이를 보고 제출하였다,,,ㅠ

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[코드트리] 정수 사각형 최솟값의 최대 , python 문제 풀이