[백준 C++] 1890 점프

점프

(0, 0)에서 (N - 1, N - 1)로 가는 경로의 수를 파악하는 문제다.  각 칸에는 그 칸으로부터 몇 칸을 움직일 수 있는지 정해져있으며, 오른쪽이나 아래로만 움직일 수 있다. 한 번에 움직일 수 있는 거리는 0보다 크거나 같고, 9보다 작거나 같다.

• 한 번에 움직일 수 잇는 거리가 0이 될 수도 있다는 점을 못봐서 한번 틀렸었다.(메모리 초과)
• 또한 가능한 경우의 수가 최대 $2^{63} - 1$이라고 제한을 줬으며, 중간값이 이 값보다 커질 가능성은 없으므로 cache는 long long 타입으로 해도 충분했다.

그 이외에는 주의할 사항이 없다.

#include <iostream>
using namespace std;
#define FOR(i, N) for (int i = 0; i < N; i++)
#define ll long long
int N;
int arr[100][100];
ll cache[100][100];
ll go(int y, int x) {
  if (y < 0 || x < 0 || y >= N || x >= N) return 0;
  if (cache[y][x]) return cache[y][x];
  if (y == N - 1 && x == N - 1) {
    return 1;
  }
  if (arr[y][x] == 0) return 0;
  return cache[y][x] = go(y + arr[y][x], x) + go(y, x + arr[y][x]);
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  cin >> N;
  FOR(i, N) {
    FOR(j, N) {
      cin >> arr[i][j];
    }
  }
  cout << go(0, 0) << '\n';
}