[백준 1890번] 점프

문제 링크: https://www.acmicpc.net/problem/1890

1890번: 점프

<문제 풀이> 다이나믹 프로그래밍(DP) 알고리즘

 

dp식을 아래와 같이 정의할 수 있습니다.

dp[i][j] : 가장 왼쪽 위 칸에서 시작해서 (i, j)까지 규칙에 맞게 이동할 수 있는 경로의 개수

 

(1, 1)은 처음 시작 위치이므로 (1,1)까지 이동할 수 있는 경로의 개수는 1입니다.

-> dp[1][1] = 1

 

dp[1][1]부터 dp[i][j]까지 dp 값이 잘 계산되었다고 생각하면

(i, j)에서 남쪽방향, 동쪽 방향의 dp값은 다음과 같이 계산할 수 있습니다.

 

남쪽 방향 = dp[i + arr[i][[j]] += dp[i][j];

동쪽 방향 = dp[i][j + arr[i][j]] += dp[i][j];

 

(i, j)까지 이동할 수 있는 경로의 개수를 알고 있다고 했을 때 다음 좌표로 점프하는 것은 (i, j)까지의 경로의 개수와 같습니다. 점프는 다른 경로로 생각하는 것이 아니라 같은 경로 이기 때문입니다.

그러나 다음 좌표로 점프하는 (i, j)가 여러 개가 존재하므로 단순히 대입하는 것이 아니라 dp[nx][ny]에 누적해야 합니다.

dp[i][j]값들은 가장 왼쪽 위 칸에서 시작해서 차례로 계산을 하기 때문에 잘 계산되어 있습니다.

 

한 가지 주의할 점은 경로의 개수는 문제에서 2^63 -1보다 작거나 같다고 했으므로 long long 배열을 선언해야 합니다.

 

<C++소스코드>

#include<iostream>
using namespace std;
 
int arr[101][101];
long long dp[101][101]; //dp[i][j] :가장 왼쪽 위 칸에서 시작해서 (i, j)까지 규칙에 맞게 이동할 수 있는 경로의 개수
 
const int dx[2] = { 1, 0 };
const int dy[2] = { 0, 1 };
 
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 >> arr[i][j];
        }
    }
 
    dp[1][1] = 1;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] == 0 || arr[i][j] == 0) continue;
            for (int dir = 0; dir < 2; dir++) {
                int nx = i + dx[dir] * arr[i][j];
                int ny = j + dy[dir] * arr[i][j];
                if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                dp[nx][ny] += dp[i][j];
            }
 
        }
    }
    cout << dp[n][n];
 
    return 0;
}