[백준 c++] 1890 점프

문제

https://www.acmicpc.net/problem/1890
N×N 게임판의 각 칸에는 현재 칸에서 갈 수 있는 거리가 적혀있다.
맨 왼쪽 위에서 출발해서 맨 오른쪽 아래로 가는게 목표다.

오른쪽 또는 아래 방향으로만 이동할 수 있고
한 칸에서 다른 칸으로 이동할 때 이동 방향을 바꿀 수 없다.

칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

---

풀이

문제 잘 읽기....난독증 GET OUT.

Top-down DP로 풀었다.
문제 풀 때 주의해야하는 점은

1. 칸에 적혀있는 수가 0일 수도 있다.
   => DP를 0으로 초기화하면 안되고 -1로 초기화 해야한다.
   -1로 초기화하면 dp[y][x]+= 로 누적합을 쓰면 안된다 (음수 나옴)

2. 경로의 개수는 최대 2^63-1
   => dp를 long long 자료형

---

코드

#include <iostream>
#include <string.h>
using namespace std;
int n, a[101][101];
long long dp[101][101];

long long go(int y, int x)
{
    if (y == n - 1 && x == n - 1)
        return 1;
    if (y >= n || x >= n || !a[y][x])
        return 0;
    if (dp[y][x] != -1)
        return dp[y][x];
    return dp[y][x] = go(y + a[y][x], x) + go(y, x + a[y][x]);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    memset(dp, -1, sizeof(dp));
    cout << go(0, 0) << "\n";
}