백준 1890 : 점프

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

1890번: 점프

N×N 게임판이 주어졌을 때, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 하고, 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 이동할 수 있는 경로의 개수를 구하는 문제였습니다. 다이나믹 프로그래밍을 통해 문제를 해결했고, 풀이 절차는 다음과 같습니다.

 

먼저, "dp[i][j] : (i, j)까지 이동할 수 있는 경로의 개수"라 한다면,

 

[1] 오른쪽으로 가는 경우 : "dp[i][j + map[i][j]]" 이고,

[2] 아래쪽으로 가는 경우 : "dp[i + map[i][j]][j]" 입니다.

 

결국,

오른쪽으로 갈 수 있다면 오른쪽으로 가는 경우에 dp[i][j] 값을 더해주어야 하고,

아래쪽으로 갈 수 있다면 아래쪽으로 가는 경우에도 마찬가지로 dp[i][j] 값을 더해주어야 합니다.

 

자세한 풀이 및 구현 방법은 코드와 주석 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
 
int n, map[100][100];
long long int dp[100][100];
 
int main(void) {
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
 
    dp[0][0] = 1;
    // dp[n-1][n-1]까지 수를 채워 나갑니다
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            // map의 값이 0이면 더 이상 이동할 수 없습니다
            if (!map[i][j]) continue;
 
            // 오른쪽으로 갈 수 있다면
            if (j + map[i][j] < n)
                // (i, j)까지 올 수 있는 경로의 수를
                // (i, j+map[i][j])까지 갈 수 있는 경로의 수에 더해줍니다
                dp[i][j + map[i][j]] += dp[i][j];
 
            // 아래쪽으로 갈 수 있다면
            if (i + map[i][j] < n)
                // (i, j)까지 올 수 있는 경로의 수를
                // (i+map[i][j], j)까지 갈 수 있는 경로의 수에 더해줍니다
                dp[i + map[i][j]][j] += dp[i][j];
        }
    printf("%lld", dp[n - 1][n - 1]);
    return 0;
}