백준 1890번 점프 - C++ 풀이

---

 

1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수
2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]]

 

1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수

 dp[r][c]를 위와 같이 정의하자. 기저사례는 도착지점인 경우가 되겠다.

 

2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]]

 각 칸에서 board[r][c]만큼 아래쪽으로 가는 방법과 오른쪽으로 가는 방법이 있으므로 이 두가지 방법으로 이동했을 때의 경로의 수를 더해주면 된다. 이때 점프 거리가 보드 밖으로 넘어가지 않는지 체크해주어야 하고, 만약 board[r][c] = 0인 경우 그 자리에서 바로 종료임에 유의하자. 또한 답은 int 범위를 벗어난다는 점 또한 주의해야 한다.

---

#include <iostream>
#include <string.h>

using namespace std;

const int MAX_N = 101;
typedef long long ll;

int N;
int board[MAX_N][MAX_N];
ll cache[MAX_N][MAX_N];

ll dp(int r, int c) {
    if (r == N-1 && c == N-1) return 1;
    
    ll& ret = cache[r][c];
    if (ret != -1) return ret;
    
    ret = 0;
    if (board[r][c] == 0) return ret;
    
    int nr = r + board[r][c];
    int nc = c + board[r][c];
    if (nr < N) ret += dp(nr, c);
    if (nc < N) ret += dp(r, nc);
    
    return ret;
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cache[i][j] = -1;
            cin >> board[i][j];
        }
    }
    
    cout << dp(0, 0);
    
    return 0;
}