백준 1890 점프 (C++)

1890번: 점프

dp를 활용한 문제이다. 처음에는 bfs로 접근을 했는데 이 문제는 bfs로는 풀 수가 없는 문제이다. 이유는 여기에 어떤 분이 정리를 잘 해주셨다. 후에 dp로 접근을 했다. 해당 좌표에 몇번 접근했는지 카운트를 해서 더해주면서 최종 카운트를 출력해주었다.

#include <iostream>

using namespace std;

int N;
int A[101][101];
long long dp[101][101];

void solution() {
    dp[0][0] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j] == 0) continue;
            if (i == N - 1 && j == N - 1) continue;
            
            int down = i + A[i][j];
            int right = j + A[i][j];

            if (down < N) {
                dp[down][j] += dp[i][j];
            }
            if (right < N) {
                dp[i][right] += dp[i][j];
            }
        }
    }

    cout << dp[N-1][N-1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}