1890번

1890번 - 점프

점프할 때마다 맵이 줄어들기 때문에, DP로 풀 수 있었다.

따라서 D[x][y] = x,y 에서 도착지에 갈 수 있는 경우의 수 

라고 점화식을 세우고 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
long long D[101][101];
int map[101][101];
int n;
long long go(int x, int y)
{
    if (x >= n || y >= n)
    {
        return 0;
    }
    if (x == n - 1 && y == n - 1)
    {
        return 1;
    }
 
    if (x != n - 1 && y != n - 1 && map[x][y] == 0)
    {
        return 0;
    }
 
    if (D[x][y] >= 0)
    {
        return D[x][y];
    }
    
    if (D[x][y] == -1)
    {
        D[x][y] = 0;
    }
    
    D[x][y] += (go(x+map[x][y],y)+go(x,y+map[x][y]));
 
    return D[x][y];
 
}
int main()
{
    cin >> n;
 
    memset(D, -1, sizeof(D));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    cout << go(0, 0) << "\n";
 
    return 0;
}