[백준] 1890번: 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

다이나믹 프로그래밍의 진행방향을 확실히 하였기에 풀기에 쉬운 문제였다.

좌에서 우로, 상에서 하로 이동하기 때문에 행, 열 우선으로 이동하며 2차원 메모이제이션을 수행한다.

여기서 중요한 점은 어떻게 메모이제이션을 쓰면 될까??

 

다이나믹 프로그래밍 시에 접근하는 칸의 숫자에 따라 경로가 정해지는 것이 아니라, 이전 경로의 숫자로 해당 칸의 접근 가능 여부가 정해진다. 따라서 이전 경로의 후보 위치를 탐색하면서 해당 칸까지의 경로의 수를 파악할 수 있다. 하지만 이전 경로 후보를 모두 방문할 필요 없고, 다이나믹 프로그래밍을 이용해 직전 후보만 파악하면 된다.

 

#include <iostream>

using namespace std;
long long arr[100][100];
long long dp[100][100] = {0};
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> arr[i][j];
        }
    }
    
    dp[0][0] = 1;
    
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) {
            for(int k = 0;k < i;k++) {
                if(arr[k][j] + k == i) {
                    dp[i][j] += dp[k][j];
                }
            }
            
            for(int k = 0;k < j;k++) {
                if(arr[i][k] + k == j) {
                    dp[i][j] += dp[i][k];
                }
            }
        }
    }
    

    cout << dp[n - 1][n - 1] << '\n';
    
    
}