격자에서 목적지까지 도달하기 위한 최소 초기 포인트 구하기

문제 개요

주어진 격자(grid)의 왼쪽 위 모서리에서 출발해 오른쪽 아래 모서리에 도달해야 합니다. 격자의 각 칸에는 숫자가 하나씩 들어 있는데, 이 값은 양수일 수도 있고 음수일 수도 있습니다. 사람이 어떤 칸 (i, j)에 도착하면, 그가 보유한 토큰 수는 해당 칸의 값만큼 증가하거나 감소합니다. 우리가 구해야 할 것은 이 여정을 끝까지 완주하기 위해 처음에 가져가야 하는 최소 초기 토큰 수입니다.

이동 규칙

이동 방향: 오른쪽 또는 아래로만 이동할 수 있습니다.
진입 조건: 보유한 총 토큰이 칸 (i, j)의 값보다 적으면 그 칸으로 들어갈 수 없습니다.
도착 조건: 목적지에는 반드시 양수 포인트(최소 1)를 가진 상태로 도착해야 합니다.

입력과 출력

입력은 각 칸의 토큰 값을 담은 행렬로 주어지고, 출력은 여정을 시작하기 위해 필요한 최소 토큰 수입니다.

입력:
각 방의 토큰 값을 행렬 형태로 입력
-2  -3   3
-5 -10   1
10  30  -5

출력:
여정을 시작하는 데 필요한 최소 토큰 → 이 예제에서는 7

알고리즘: 동적 계획법으로 접근하기

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 도착점에서 거꾸로 거슬러 올라가면서, 각 칸에 도달했을 때 이후 경로를 완주하는 데 필요한 최소 토큰을 미리 계산해 두는 것입니다.

각 칸 (i, j)에서 필요한 최소 토큰은 다음과 같이 정의됩니다.

오른쪽 칸과 아래 칸 중 요구 토큰이 더 작은 쪽을 선택합니다(rem).
현재 칸의 값을 뺀 결과와 1 중 더 큰 값을 저장합니다. 어떤 경우에도 최소 1포인트는 유지해야 하기 때문입니다.

알고리즘 의사 코드

minInitTokens(matrix)

입력: 각 칸의 토큰 값 행렬
출력: 시작점에서 목적지까지 도달하는 데 필요한 최소 토큰

Begin
    matrix와 같은 크기의 minToken 행렬을 정의한다
    m := matrix의 행 개수
    n := matrix의 열 개수

    // 도착 칸 처리
    if matrix[m-1, n-1] > 0 then
        minToken[m-1, n-1] := 1
    else
        minToken[m-1, n-1] := 1 + |matrix[m-1, n-1]|

    // 마지막 열을 아래에서 위로 채운다
    for i := m-2 down to 0 do
        minToken[i, n-1] := max(1, minToken[i+1, n-1] - matrix[i, n-1])
    done

    // 마지막 행을 오른쪽에서 왼쪽으로 채운다
    for j := n-2 down to 0 do
        minToken[m-1, j] := max(1, minToken[m-1, j+1] - matrix[m-1, j])
    done

    // 나머지 칸을 오른쪽 아래에서 왼쪽 위로 채운다
    for i := m-2 down to 0 do
        for j := n-2 down to 0 do
            rem := min(minToken[i+1, j], minToken[i, j+1])
            minToken[i, j] := max(1, rem - matrix[i, j])
        done
    done

    return minToken[0, 0]
End

C++ 구현 예제

#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
    {-2,-3,3},
    {-5,-10,1},
    {10,30,-5}
};

int max(int a, int b) {
    return (a > b) ? a : b;
}

int minInitPoints() {
    int minToken[ROW][COL];
    int m = ROW, n = COL;

    // 도착 칸: 값이 양수면 1, 아니면 절댓값 + 1
    minToken[m-1][n-1] = tokens[m-1][n-1] > 0 ? 1 : abs(tokens[m-1][n-1]) + 1;

    // 마지막 열을 아래에서 위로 채움
    for (int i = m-2; i >= 0; i--)
        minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);

    // 마지막 행을 오른쪽에서 왼쪽으로 채움
    for (int j = n-2; j >= 0; j--)
        minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

    // 나머지 칸을 채우며 필요 포인트 계산
    for (int i = m-2; i >= 0; i--) {
        for (int j = n-2; j >= 0; j--) {
            int remPoint = min(minToken[i+1][j], minToken[i][j+1]);
            minToken[i][j] = max(remPoint - tokens[i][j], 1);
        }
    }
    return minToken[0][0];
}

int main() {
    cout << "필요한 최소 포인트: " << minInitPoints();
}

실행 결과

필요한 최소 포인트: 7

예제 검증: DP 테이블 살펴보기

위 알고리즘을 예제 행렬에 적용하면 다음과 같은 minToken 테이블이 만들어집니다.

 7   5   2
 6  11   5
 1   1   6

예를 들어 도착 칸의 값이 -5이므로 최소 6토큰이 필요하고, 바로 위 칸(값 1)에서는 6 − 1 = 5토큰, 왼쪽 칸(값 30)에서는 30을 얻으므로 최소치인 1토큰만 있으면 충분합니다. 이런 식으로 거꾸로 계산해 올라가면 시작 칸에서 5 − (−2) = 7, 즉 처음에 7토큰을 가지고 출발해야 한다는 결론이 나옵니다.

이 알고리즘의 시간 복잡도는 O(m×n), 공간 복잡도 역시 O(m×n)으로, 격자의 모든 칸을 단 한 번씩만 방문하면 되기 때문에 매우 효율적입니다.