[백준/C++] 1890번: 점프

문제

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

---

문제 요약

N × N 게임판에 수가 적혀져 있다.

 

각 칸에 적힌 숫자는 현재 칸에서 이동할 수 있는 거리를 의미한다.

(반드시 적힌 숫자만큼 이동해야한다.)

 

항상 현재 칸에 적힌 숫자만큼 오른쪽이나 아래로 가야한다.(이동 중 방향을 바꿀 수는 없다.)

 

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로 개수를 출력한다.

---

코드

#include <iostream>

#define ll long long
using namespace std;

ll board[110][110];
ll dp[110][110];
ll n;

// (x, y)에서 (n - 1, n - 1)에 도착할 수 있는 경로 수 반환
ll dfs(ll x, ll y) {
    if (x >= n || y >= n) return 0;
    if (x == n - 1 && y == n - 1) return 1;

    if (dp[x][y] != -1) return dp[x][y];

    ll max_move = board[x][y];
    dp[x][y] = 0;

    // 아래로 이동
    if (x + max_move < n) {
        dp[x][y] += dfs(x + max_move, y);
    }

    // 오른쪽으로 이동
    if (y + max_move < n) {
        dp[x][y] += dfs(x, y + max_move);
    }

    return dp[x][y];
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            dp[i][j] = -1;
        }
    }

    cout << dfs(0, 0);
}

---

코드 설명

1. 게임판에 적힌 숫자 정보를 2차원 배열에 입력 받는다.

 

2. dp[i][j]에 (i, j)에서 (n - 1, n - 1)까지 이동할 수 있는 경로 수를 저장한다. (초기 값: -1)

 

3. 재귀함수 dfs를 통한 Top Down DP로 dp[0][0]을 구한다.

 

4. 범위를 벗어는 경우, 경로가 없으므로 0을 반환한다.

 

5. (n - 1, n - 1)에서 (n - 1, n - 1)까지, 즉 가장 오른쪽 아래 칸에 도착했으면 1을 반환한다.

6. dp 메모이제이션 테이블을 통해 이미 구한 적이 있는 dfs는 진행하지 않는다.

---

고찰

각 칸에 적힌 수가 현재 칸에서 갈 수 있는 거리라고 적혀있길래,

더 조금씩도 이동할 수 있다고 생각해서 풀었다가 알아채는데 시간이 걸렸다.

 

위 코드 설명의 5번(기저)을 떠올리기 어려웠다.

 

마지막으로, 경로의 수가 int형으로 표현 불가하기 때문에 long long을 사용해야 한다.