알고리즘/백준

1890 점프

아메숑 2019. 3. 19. 05:21

1. 문제



2. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <queue>
#include <iostream>
 
using namespace std;
 
int N;
int map[101][101];
long dp[101][101];
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j] == 0 || (i == N - 1 && j == N - 1))
                continue;
 
            int plus = map[i][j];
 
            //down
            if (i + plus < N)
                dp[i + plus][j] += dp[i][j];
 
            //right
            if (j + plus < N)
                dp[i][j + plus] += dp[i][j];
            
        }
    }
 
    cout << dp[N - 1][N - 1];
 
}
cs


3. 후기

처음에 비슷하게 작성했지만 += dp[i][j] 이부분을 +=1로 해서 틀렸다. 

그리고 dp배열을 long으로 잡아야했다. 경로의 경우의 수는 크기가 100까지 가면 아마 경로가 엄청 많아지기 때문인것 같다.