[코드트리 챌린지] 4주차 DP l - 격자 안에서 한 칸씩 전진하는 DP / 정수 사각형 최솟값의 최대

투포인터인걸 알아내긴 했는데 풀 줄 몰라서 틀려버렸다.. 이진탐색은 풀어본 경험이 있어서 운좋게 풀 수 있었다!

https://www.codetree.ai/missions/2/problems/maximin-path-in-square/description

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

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[105][105];
int dp[105][105];

void Initialize() {
    dp[0][0] = arr[0][0];

    // 한칸 이전 것과 자신을 비교하여 작은 것들로 dp 배열 채움
    for (int i = 1; i < n; i++) {
        dp[i][0] = min(dp[i - 1][0], arr[i][0]);
    }
    for (int i = 1; i < n; i++) {
        dp[0][i] = min(dp[0][i - 1], arr[0][i]);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    Initialize();

    // 최소값 중 가장 큰 값을 선택해야하므로
    // 왼,위쪽 두 수 중 큰 값과 현 위치 값 중 작은 값을 dp 배열에 채움
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            int tmp = max(dp[i - 1][j], dp[i][j - 1]);
            dp[i][j] = min(tmp, arr[i][j]);
        }
    }

    cout << dp[n - 1][n - 1];

}

n을 입력받고 이중 for문을 통해 주어진 행렬을 입력받습니다.

Initialize() 함수를 통해 (0,0) 부터 (0, n-1), (n-1, 0) 부분의 dp값을 모두 채웁니다.
(0,i)나 (i,0) 같은 경우 바로 한 칸 이전 값과 자신의 값을 비교하여 dp 배열을 채울 수 있으므로
별다른 점화식 없이 가능합니다.

나머지 dp 배열을 채울 때 우리는 최소값이 가장 크게 되도록 dp 배열을 채워야만 합니다.
그러기 위해선 dp[i][j] 값을 채울 때 dp[i-1][j], dp[i][j-1] 중 큰 값을 가져와서 비교해야만 합니다.
(최소값 중 가장 커야하기 때문) 이후 arr[i][j]값과 비교하여 작은 값을 선택해 dp를 채운다면
최소값이 가장 크게 되도록 dp 배열을 구성할 수 있습니다.