BOJ)1890 점프

문제: icpc.me/1890

규칙에 맞게 갈 수 있는 경로가 주어질 때 오른쪽 맨 아래로 가는 경우의 수를 계산해주는 문제이다.

우리는 dp[x][y] = 0,0에서 x,y로 가는 경우의 수로 테이블을 잡아 준 뒤

x,y에서 나보다 x좌표나 y좌표가 작은 지역중 나에게로 올 수 있는 경우의 수를 더해줘서 n^3 다이나믹 프로그래밍으로 구해줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, dp[101][101], a[101][101];
ll func(int x, int y) {
    if (x == y&&y == 0)return 1;
    ll &ret = dp[x][y];
    if (ret != -1)return ret;
    ret = 0;
    for (int i = x - 1; i >= 0; i--) 
        if (a[i][y] == x - i)
            ret += func(i, y);
    for (int i = y - 1; i >= 0; i--) 
        if (a[x][i] == y - i)
            ret += func(x, i);
    return ret;
}
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            scanf("%lld", &a[i][j]);
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld\n", func(n - 1, n - 1));
    return 0;
}