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

📖 문제

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

 

 

 

💡  풀이 방식

• DP

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

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

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

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

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

 

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

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

(= 최댓값을 최소로)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int[][] 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());
            }
        }
 
        int[][] dp = new int[N][N];
        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.max(Math.min(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

---

(참고)

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