1890 점프

1890. 점프 / c++ / Silver1 / 35분

문제

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

1. N x N 게임판에 수가 적혀있다. (0 ~ 9)
2. 각 칸에 적혀있는 수 만큼 ‘아래’ 혹은 ‘오른쪽’ 으로만 점프할 수 있다.
3. 1,1 칸에서 N,N칸으로 이동할 수 있는 경우의 수는?

접근 방식

동적 프로그래밍

1. 임의의 칸 i, j에 대해 최대 9칸 ‘왼쪽’, ‘윗쪽’까지 탐색한다.
2. 만약 해당칸의 숫자가 해당칸에서 i,j칸까지의 거리와 같다면 += DP(i,j) 해준다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

int N;

int board[100][100] = {};
unsigned long long dp[100][100] = {};

unsigned long long DP(int y, int x)
{
    if (dp[y][x] == 0)
    {
        for (int i = 0; i < y; ++i)
        {
            if (board[i][x] == y - i)
            {
                dp[y][x] += DP(i, x);
            }
        }
        for (int j = 0; j < x; ++j)
        {
            if (board[y][j] == x - j)
            {
                dp[y][x] += DP(y, j);
            }
        }
    }

    return dp[y][x];
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> board[i][j];
        }
    }

    dp[0][0] = 1;

    cout << DP(N-1, N-1) << '\n';

    return 0;
}

다시 생각해 볼 점

1. 경우의 수는 2^63 - 1이므로 자료형을 long long을 했어야 했는데, int를 사용해서 틀렸었다.
2. DP함수의 반환형도 long long으로 바꿨어야했는데, dp배열만 바꾸고 반환형을 바꾸지 않아서 계속 틀렸었다.
3. 자료형의 범위를 항상 생각하자.