[1890] 점프

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

이 문제는 어렵지 않았습니다.

dp라고 알 수 있는 부분은 이 문제가 경우의 수이고, 정답이 2^63이라면 DP를 제외하고는 시간안에 풀 수 없습니다.

dp라는 것만 안다면 어렵지 않은 문제입니다.

#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
 
int map[100][100];
ll dp[100][100];
 
int n;
 
ll f(int x, int y) {
    if (x == n - 1 && y == n - 1) {
        return 1;
    }
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
        if (nx >= n || ny >= n) continue;
 
        ret += f(nx, ny);
    }
 
    return ret;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
 
    cout << f(0, 0);
 
    return 0;
}