BOJ - 점프(1890)

실버2 : 동적 계획법 문제이다.

생각

앞으로 보내는 dp문제이다.

정의

이 문제는 위치에 따라 개수가 결정되므로 dp의 인자를 좌표의 위치로 잡는 것이 수월하다.

dp[y][x] = (y,x) 위치까지 도착하는 경로의 개수

점화식

해당 위치까지 도착하는 개수는 이전 위치에서 올 수 있느냐를 판단해야 한다. 이 경우 과거로 부터 현재를 갖고오는 것이 무리가 있으니 오히려 현재 위치에서 다음 위치로 갈 수 있는 경로를 업데이트 하는 것이 옳다.

dp[y+d][x] += dp[y][x]

dp[y][x+d] += dp[y][x]

d는 (y,x)위치에서 점프할 수 있는 크기이다. 이 때 dp[y][x]로 업데이트 해주는 이유는, 해당 (y, x) 위치에 도착할 수 있는 경로가 2개라면, 이 지점까지 도달한 경로 모두는 다음 위치로 이동할 수 있기 때문에 그 숫자로 업데이트하는 것이 맞다.

4
2 3 2 1
1 2 1 3
2 2 1 1
3 1 1 0

=========(1,1 )=========
=========y 방향=========
1 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0

=========(1,1 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0

=========(1,3 )=========
=========y 방향=========
1 0 1 0
0 0 0 0
1 0 1 0
0 0 0 0

=========(1,3 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 1 0
0 0 0 0

=========(3,1 )=========
=========y 방향=========
1 0 1 0
0 0 0 0
1 0 1 0
0 0 0 0

=========(3,1 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 2 0
0 0 0 0

=========(3,3 )=========
=========y 방향=========
1 0 1 0
0 0 0 0
1 0 2 0
0 0 2 0

=========(3,3 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 2 2
0 0 2 0

=========(3,4 )=========
=========y 방향=========
1 0 1 0
0 0 0 0
1 0 2 2
0 0 2 2

=========(3,4 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 2 2
0 0 2 2

=========(4,3 )=========
=========y 방향=========
1 0 1 0
0 0 0 0
1 0 2 2
0 0 2 2

=========(4,3 )=========
=========x 방향=========
1 0 1 0
0 0 0 0
1 0 2 2
0 0 2 4

4

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int N;
int map[101][101];
ll dp[101][101];
 
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    dp[N][N] = 0;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            if (dp[y][x] == 0 || (y == N && x == N)) continue;
            int d = map[y][x];
            if (y+d <= N) dp[y+d][x] += dp[y][x];
            if (x+d <= N) dp[y][x+d] += dp[y][x];
        }
    }
    cout << dp[N][N] << '\n';
}
 

Reference

• 백준(1890번) - 점프