1890 점프

1. 문제

2. 코드

#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];
 
}

3. 후기

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

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