백준 1890 점프(dynamic programming)

https://www.acmicpc.net/problem/1890

1890번: 점프

#include <iostream>

using namespace std;

const int MAX = 100 + 1;
int N;
int arr[MAX][MAX];
long long dp[MAX][MAX];
void findway()
{
    dp[0][0] = 1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (arr[i][j] == 0)
                continue;
            if (i + arr[i][j] < N)
                dp[i + arr[i][j]][j] += dp[i][j];
            if (j + arr[i][j] < N)
                dp[i][j + arr[i][j]] += dp[i][j];
        }
    }
    cout << dp[N - 1][N - 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
    findway();
}

그렇게 어려운 것은 없었고 논리 자체도 단순하다. 작은 부분부터 계산해서 점점 키워나가는 dynamic programming 특성상 갈 수 있는 방향인 오른쪽과 아랫쪽만 정의해놓으면 됐다.