이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 58 번째 글 입니다.
목차
실버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';
}