문제 설명
악마들이 이름이 P인 공주를 납치해 던전의 오른쪽 맨 아래 방에 가두었다는 이야기를 상상해 봅시다. 던전은 M행 × N열의 격자 형태 방으로 이루어져 있으며, 용감한 기사 K는 왼쪽 맨 위 방에서 출발해 공주를 구출하기 위해 던전을 돌파해 나가야 합니다.
기사는 양의 정수로 표현되는 초기 체력(HP)을 가지고 시작합니다. 진행 도중 어느 시점에서든 체력이 0 이하로 떨어지면 그 자리에서 즉시 사망합니다.
일부 방에는 악마가 지키고 있어 들어가는 순간 체력이 깎이고(음의 정수), 어떤 방은 비어 있거나 체력을 회복시켜 주는 마법 구슬이 놓여 있습니다(양의 정수).
공주에게 최대한 빨리 도달하기 위해 기사는 매 단계마다 오른쪽 또는 아래쪽으로만 이동하기로 합니다. 우리가 구해야 하는 값은 공주에게 무사히 도달하기 위해 필요한 최소 초기 체력입니다.
예를 들어 아래와 같은 던전이 주어졌다면 정답은 6입니다. 기사가 오른쪽 → 오른쪽 → 아래 → 아래 경로로 이동하면 체력이 6 → 4 → 2 → 5 → 6 → 1로 변해 끝까지 0 이하로 떨어지지 않기 때문입니다.
| -2(K) | -2 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5(P) |
풀이 접근 방법
이 문제는 오른쪽 아래(공주의 위치)에서 왼쪽 위(기사의 출발점)로 거꾸로 거슬러 올라가는 동적 계획법(DP)으로 해결할 수 있습니다. 입력 배열 dp를 그대로 활용해 각 칸에서 출발했을 때의 최적 값을 갱신하면서 최소 초기 체력을 역산합니다.
구체적인 절차는 다음과 같습니다.
- r := dp의 행 개수, c := dp의 열 개수로 설정합니다.
- j := r - 2부터 시작해 j >= 0이 될 때까지 j를 1씩 줄이며 반복합니다.
- dp[j, c-1] := dp[j, c-1]과 dp[j, c-1] + dp[j+1, c-1] 중 최솟값
- j := c - 2부터 시작해 j >= 0이 될 때까지 j를 1씩 줄이며 반복합니다.
- dp[r-1, j] := dp[r-1, j]와 dp[r-1, j] + dp[r-1, j+1] 중 최솟값
- i := r - 2부터 시작해 i >= 0이 될 때까지 i를 1씩 줄이며, 안쪽 루프에서 j := c - 2부터 j >= 0이 될 때까지 반복합니다.
- dp[i, j] := dp[i, j]와 max(dp[i, j] + dp[i+1, j], dp[i, j] + dp[i, j+1]) 중 최솟값
- 반복이 끝난 후 dp[0, 0] <= 0이면 |dp[0, 0]| + 1을 반환합니다.
- 그렇지 않으면 1을 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli min(lli a, lli b){
return a <= b ? a : b;
}
lli max(lli a, lli b){
return a <= b ? b : a;
}
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dp) {
int r = dp.size();
int c = dp[0].size();
for(lli j=r-2;j>=0;j--){
dp[j][c-1] = min(dp[j][c-1], dp[j][c-1]+dp[j+1][c-1]);
}
for(lli j = c-2;j>=0;j--){
dp[r-1][j] =min(dp[r-1][j], dp[r-1][j]+dp[r-1][j+1]);
}
for(lli i = r-2;i>=0;i--){
for(lli j = c-2;j>=0;j--){
dp[i][j] = min(dp[i][j],max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i][j+1]));
}
}
if(dp[0][0] <= 0 )return abs(dp[0][0])+1;
return 1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
cout << (ob.calculateMinimumHP(v));
}입력
{{-2,-2,3},{-5,-10,1},{10,30,-5}}출력
6
정리
이 풀이는 배열을 제자리(in-place)에서 갱신하므로 별도의 추가 공간 없이 처리되며, 격자의 모든 칸을 한 번씩 방문하므로 시간 복잡도는 O(M×N)입니다. 최종적으로 dp[0][0]의 값이 양수라면 초기 체력 1만으로도 충분하고, 0 이하라면 부족한 만큼 1을 더한 값이 곧 기사가 가져가야 할 최소 초기 체력이 됩니다.