[C++] DP - 알리바바와 40인의 도둑

 

#include <iostream>
#include <queue>

using namespace std;

int map[21][21];
int dy[21][21];
int main() {
    ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> map[i][j];
        }
    }
    
    dy[1][1] = map[1][1];
    for(int i = 2; i <= N; i++){
        dy[1][i] = dy[1][i-1] + map[1][i];
        dy[i][1] = dy[i-1][1] + map[i][1];
    }
    
    for(int i = 2; i <= N; i++){
        for(int j = 2; j <= N; j++){
            dy[i][j] = min(dy[i-1][j],dy[i][j-1]) + map[i][j];
        }
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cout << dy[i][j]<<" ";
        }
        cout << endl;
    }
    
}

• DP문제는 작은 문제의 해를 이용하여 큰 문제를 해결하는 문제라는 것을 잊지 말자

풀이

1. 직관적으로 알 수 있는 작은 문제의 해는 무엇이 있을까 생각한다.

   1) 출발지점의 해

   2) 오른쪽과 아래로만 이동이 가능하므로, 출발점으로부터 수직,수평에 속하는 행과 열의 모든 값

     - dy[1,2]는 무조건 dy[1,1]에서만 올 수 있다. dy[1,5]는 무조건 dy[1,4]에서만 올 수 있다....

2. dy테이블에 할당된 값을 기준으로 dy[2,2]부터 시작해도 된다는 것을 알 수 있고, 위쪽과 왼쪽 중, 작은 값을 현재 자기 자신arr[i][j]의 값과 더하면 된다는 것을 알 수 있다.(dy[1,2]와 dy[2,1]에는 이미 최선의 값(정답)이 들어있기 때문에 가능한 것이다.bottom-up)

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard