[C/C++] 백준 #1890 점프(동적 계획법)

이번 문제는 동적 계획법을 이용해서 풀었습니다.  사실 동적 계획법이 아니라 너비 우선 탐색(BFS)를 사용해도 같은 결과를 얻을 수 있습니다.  그렇지만 단순 반복문을 사용할 수 있는 동적 계획법에 비해서 효율이 떨어지게 되겠죠.

 

jump

 

동적 계획법 알고리즘은 간단합니다.  \(d_{i, j} \)를 시작점에서 \((i, j)\)로 가는 경로의 개수라고 한다면,

 

1. NxN 공간을 0으로 초기화합니다.  \( d_{i, j} = 0 \)

2. 시작점을 1로 놓습니다.  즉, 시작점에서 시작점으로 가는 경로는 한가지입니다.  \(d_{0, 0} = 1\)

3. 시작점에서부터 오른쪽 방향 우선으로, 아래로 이동하면서 갈 수 있는 모든 곳 \(d_{i+a_{i, j}, j}\) 값과 \(d_{i, j+a_{i, j}}\) 값을 현재 공간의 값만큼 증가시킵니다.

4. 도착점에 계산된 값이 결과값이 됩니다.

 

2/1	3/0	3/0	1/0
1/0	2/0	1/0	3/0
1/0	2/0	3/0	1/0
3/0	1/0	1/0	0/0

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/0	3/0	1/0
3/0	1/0	1/0	0/0

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/0	3/0	1/0
3/0	1/0	1/1	0/0

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/1	3/0	1/0
3/1	1/0	1/1	0/0

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/1	3/0	1/1
3/1	1/0	1/1	0/0

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/1	3/0	1/1
3/1	1/0	1/1	0/1

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/1	3/0	1/1
3/1	1/0	1/1	0/2

 

2/1	3/0	3/1	1/0
1/0	2/0	1/0	3/0
1/1	2/1	3/0	1/1
3/1	1/0	1/1	0/3

 

이렇게 동적 프로그래밍 과정을 거치면 답 3을 얻게 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1890
//        - by Aubrey Choi
//        - created at 2019-09-17
//------------------------------------------------
#include <stdio.h>

int v[100][100];
long long dp[100][100];
int main()
{
    int n, s;
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&v[i][j]);
    dp[0][0]=1;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
    {
        if((s=v[i][j])==0||dp[i][j]==0) continue;
        if(i+s<n) dp[i+s][j]+=dp[i][j];
        if(j+s<n) dp[i][j+s]+=dp[i][j];
    }
    printf("%lld\n", dp[n-1][n-1]);
}