[BOJ 백준] 1890번 점프

문제

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

1890번: 점프

접근

 이 문제의 최대 경로의 수는 2^63 -1 이하인 것만 봐도 다이나믹 프로그래밍(이하 DP)을 통해 문제를 풀어야 함을 알 수 있다. DP에서 메모이제이션(memoization)을 통해 중복된 경우를 잘 제거해주지 않는다면 수많은 경우를 반복하여 방문하기 때문에 메모리 초과, 시간 초과가 날 수 있다. 

 

 이 문제를 풀면서 간과하기 쉬운 점은 도착점 뿐만 아니라 다른 위치에도 '0'이 쓰여있을 수 있다는 사실이다. 즉, 게임판에서 도착점이 아닌 임의의 지점에 도달했을 때 0이 쓰여있다고 가정해보자. 0에 대해 따로 예외처리를 하지 않았다면 코드는 '0만큼 오른쪽으로 전진' 하거나 '0만큼 아래로 전진' 할 텐데 0만큼 전진해 봤자 제자리일 것이다. 결론적으로 같은 위치를 무한으로 호출하게 되는 일이 발생할 수 있다. 따라서 '0'에 대해 예외처리를 해줘야 한다.

 또 한 가지 실수하기 쉬운 점은 처음에 짚고 넘어갔듯 이 문제의 최대 경로의 수는 2^63 -1 이하로 결과값을 저장하는 변수는 int형이 아닌 long long형이어야 한다. 

코드

#include <iostream>
#define endl "\n"

using namespace std;

int n, map[105][105];
long long dp[105][105] = {0};

long long rec(int x, int y) {
    if (dp[x][y] != -1)
        return dp[x][y];
    if (x == n - 1 && y == n - 1)
        return 1;
    if (map[x][y] == 0)
        return dp[x][y] = 0;

    long long d1 = 0, d2 = 0;
    if (x + map[x][y] < n)
        d1 = rec(x + map[x][y], y);
    if (y + map[x][y] < n)
        d2 = rec(x, y + map[x][y]);
    return dp[x][y] = d1 + d2;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
    cout << rec(0, 0);
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study