코드트리 : 정수 사각형 차이의 최소 2

https://www.codetree.ai/missions/2/problems/minimum-difference-on-the-integer-grid-2/description

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

 

ㅎ...... 어렵다 어려워,,,

 

문제에서 주어지는 데이터의 제한을 잘 확인하자!!

이렇게 적은 숫자면,,, 좀 더 잘 생각할 필요가 있다.

 

|최댓값-최솟값|을 최소로 만든다는것...은

최댓값을 고정시켰을 때 : 최솟값을 최대로

최솟값을 고정시켰을 때 : 최댓값을 최소로...

이렇게 생각해주면 된다!

 

최솟값을 고정하고, 최대를 처리해주는게 해설의 방식이었다.

=> 그러면,, 모든 최솟값 경우의 수에 대해 탐색을 진행해주면 된다!

 

=> 이게 가능한 이유는?? 바로바로 n의 개수가 100개 이하로 적을뿐 아니라

주어지는 숫자도 100으로 한정되기 때문이다!

즉 가능한 모든 최솟값 (1 ~ 100)을 완전탐색해도 문제가 없다

 

최솟값을 고정하려면 어떻게 해야할까?

내가 임의로 정해두고, 그 숫자 "이상"인 칸으로만 이동하면 된다

 

 

test_min보다 작은 칸의 경우, 무시를 해야한다 (즉 경로에 포함되지 않도록!)

=> 이부분 처리가 미흡해서 한참을 삽질했다........... 으앙

 

---

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    // 여기에 코드를 작성해주세요.
    int n;
    cin >> n;
    vector<vector<int>> nums(n, vector<int>(n, 0));
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            cin >> nums[i][j];
        }
    }


    int result = INT_MAX;
    for(int test_min = 1; test_min<=100; test_min++){
        

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(nums[i][j] < test_min){
                    // test_min보다 큰애들만 있어야함! (test_min을 최소값으로 고정)
                   nums[i][j] = INT_MAX;
                }
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                dp[i][j] = INT_MAX;
            }
        }

        dp[0][0] = nums[0][0];
        for(int i = 1; i<n; i++){
            dp[i][0] = max(dp[i-1][0], nums[i][0]);
        }
        for(int i = 1; i<n; i++){
            dp[0][i] = max(dp[0][i-1], nums[0][i]);
        }
       
        for(int i = 1; i<n; i++){
            for(int j = 1; j<n; j++){
                dp[i][j] = max(min(dp[i-1][j], dp[i][j-1]), nums[i][j]);
            }
        }

        if(dp[n-1][n-1] == INT_MAX){
            // test_min을 최소로 만드는 경로가 하나도 없는것!
            continue;
        }

        result = min(result, (dp[n-1][n-1] - test_min));
    }
    cout << result;

    return 0;
}