(H - 174. Dungeon Game) 거꾸로 생각해보는 DP

Top-leftmost 시작 지점에서 기사가 출발해서, Bottom-rightmost 에 있는 공주를 구출하려고 한다 

여러 칸에는 양수 혹은 음수가 적혀 있으며, 기사가 해당 칸을 지날 때마다 기사의 HP에 칸에 적힌 숫자가 더해진다.

이동 중, 기사의 HP가 0이하로 떨어지면 안된다.

이때, 출발 시 기사 HP의 최솟값은?

 

---

내 풀이 - 정석적으로 출발 지점에서 출발. 

 

출발 시 HP를 0으로 두고, 각 경로의 최솟값을 계속 기록해나가면서 마지막 도착 지점에 도착할 때 경로 최솟값이 가장 큰 경로를 택하면 된다고 생각.

ex) 경로 A를 지나는데 HP가 -20까지 떨어지고, 경로 B를 지나는데 -5까지 떨어진다면, 경로 B를 택하고 초기 HP를 6으로 설정하면 되겠지.

 

DP[i][j] = 시작 지점 ~ (i, j) 까지의 경로 중 최솟값

DP[i][j] = max(DP[i-1][j], DP[i][j-1]) (즉, 최솟값이 더 큰 경로 선택)

 

근데 여기서 문제가 생김.

 

문제점 1)

min값을 저장하는 DP에서는, 이전 DP값을 가지고 현재 DP값을 구할 수 없는 경우 생김. 점화식이 안세워짐.

무슨 말이냐, 경로의 최솟값을 업데이트하기 위해서는 누적 value 값이 필요함 (val + board[x][y] < min인 경우 업데이트).

즉, min값 뿐만 아니라, 시작 지점 ~ 해당 칸 까지의 누적 value 값을 알아야 함.

 

우리 DP는 현재 '경로 min'값 밖에 없는데, min값 업데이트를 위해선 누적 val 데이터도 필요하다.

 

아 그럼 그냥 누적 val 트래킹하는 보조 행렬 만들면 되는거 아님?

→ ㅇㅇ 그럼 min 업데이트 문제는 해결.

 

근데 바로 또 반례 생겨버리죠?

 

문제점 2) 

이번에는 DP값을 결정하는데 있어서, 과연 '더 큰 최솟값을 가지는 경로'를 선택하는게 옮을까에 대한 의문에서 출발.

(어찌보면 그리디의 정당성 증명과 비슷; 반례 찾기)

min값이 더 큰 경로 B를 선택해야 할 것 같지만, 사실 경로 A를 선택해야 global optimum

위 반례를 보면, 경로 B가 min값이 더 크기에 우리 알고리즘은 경로 B를 선택한다.

하지만, 사실 min값이 더 작은 경로 A를 선택해야, (2,2)를 밟았을 때 최종 min값이 더 크게 된다.

 

이런 일이 일어나는 이유는 바로 서로 다른 val 값 때문이다.

min이 더 작더라도 val이 크면, 추후 경로에서 min값이 더 작은 값으로 업데이트 되는 것을 잘 막아내기 때문이다.

즉, 우리는 점화식을 세울 때 단순히 더 큰 min 값만 찾는게 아니라, val값도 고려해야한다.

 

 

그럼 이제 어떤 경로를 선택해야 해?

일단 위 반례에서 나타난 상황은, min값이 더 작지만 val이 더 큰 경우이다.

다시 말해, min값이 클수록 좋은건 여전하지만, min값이 작아도 val이 더 큰 경우만 추가로 고려해주면 된다.

 

일단 선택할 수 있는 경로들을 '내림차순' 정렬 해서, min값이 가장 작은 경로를 선택하자.

(-30, 10)은 (-20, -10) 보다는 min이 작지만, val이 커서 살려줌. (-40, 15)는 (-30, 10) 보다 min 작지만 val이 커서 살려줌

이후, min값이 더 작지만, val이 큰 경로들은 살려준다.

 

DP의 구조도 바꿔야 한다. 각 칸이, 여러 경로 (min, val pair로 표현됨) 들을 저장할 수 있도록.

vector<pii> dp[200][200];

using pii = pair<int, int>;

class Solution {
public:
    int N, M;
    vector<pii> dp[200][200]; // (min, val) pair
        
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        this->N = dungeon.size();
        this->M = dungeon[0].size();
        //dp = fill_n(&dp[0][0], 200*200, vector<pii>())
        
        dp[0][0].emplace_back(dungeon[0][0], dungeon[0][0]);
        for(int row = 1; row < N; row++) {
            int new_val = dp[row-1][0][0].second + dungeon[row][0];
            dp[row][0].emplace_back(min(dp[row-1][0][0].first, new_val), new_val);
        }
        for(int col = 1; col < M; col++) {
            int new_val = dp[0][col-1][0].second + dungeon[0][col];
            dp[0][col].emplace_back(min(dp[0][col-1][0].first, new_val), new_val);
        }
        
        
        for(int row = 1; row < N; row++){
            for(int col = 1; col < M; col++){
                vector<pii>& v = dp[row][col];
                
                // Route coming from up-block
                vector<pii>& up_v = dp[row-1][col];
                sort(up_v.begin(), up_v.end(), std::greater<>());
                int val_lowLimit = -1e9;
                for(int idx = 0; idx < up_v.size(); idx++){
                	// 문제점 2 해결 - pick one with higher val, ignore others
                    int prev_val = up_v[idx].second;
                    if(prev_val > val_lowLimit){
                        val_lowLimit = prev_val;
                        int new_val = prev_val + dungeon[row][col]; 
                        v.emplace_back(min(up_v[idx].first, new_val), new_val);
                    }
                }

                // Route coming from left-block
                vector<pii>& left_v = dp[row][col-1];
                sort(left_v.begin(), left_v.end(), std::greater<>());
                val_lowLimit = -1e9;
                for(int idx = 0; idx < left_v.size(); idx++){
                    int prev_val = left_v[idx].second;
                    if(prev_val > val_lowLimit){
                        val_lowLimit = prev_val;
                        int new_val = prev_val + dungeon[row][col]; 
                        v.emplace_back(min(left_v[idx].first, new_val), new_val);
                    }
                }
                
                // There are some cases that we can't decide which path is better at this stage
                // -> Just take everything into consideration
            }
        }
        
        vector<pii>& final_v = dp[N-1][M-1];
        sort(final_v.begin(), final_v.end(), std::greater<>());
        int min_life = final_v[0].first;
        cout << min_life;
        return (min_life < 0 ? -min_life + 1 : 1); // If route doesn't have any negatives, 1 is enough 
    }
};

풀이 메모

최종 값이 막 +90 이라고 초기 HP가 1이면 안되는게, 
중간 중간에 HP가 마이너스로 내려갈 수 있음. 맨 마지막에 대형 포션 먹어서 저렇게 될 수도 있음
→ Route 중 나타난 min값 계속 tracking 해서 가져가기;

어떤 경로가 가장 좋은가? => 경로 중 나타난 min값 (min_tracker)이 가장 큰 경로
(x,y)를 밟음으로써 min값이 업데이트 됨 (지금 값이 경로 중 최소) / 그대로 유지

위/왼쪽 둘 중 어느 경로가 좋아? => 최종 min_tracker 값이 더 '큰' 경로
Optimal subproblem : min값이 작은 경로가 min값이 더 큰 경로보다 좋을 이유가 전혀 없다.
과연 그럴까?
-> 만약 경로 A는 지금은 min값이 더 작지만, value값은 엄청 커서 그 min보다 떨어지지 않는데,
경로 B는 지금 min값이 더 큰 대신, value값이 매우 작아서 나중가서 min값이 A보다 떨어지면?

반례) [[-5, -10], [-15, 5], [50, 0], [-1000, -40]]
(2,1) 칸에서, min값이 더 큰 Up 경로가 더 좋아보이지만,
Goal에 해당하는 (3,1)칸에 가면, (2,1) 칸에서 min값이 더 작은 Left 경로를 택하는게 맞았음
(Left 경로의 누적 val이 더 커서, 마지막 Goal에서 마이너스 폭탄 맞았을 때, 잘 버팀)

 

---

다른 풀이 - 반대로 이동하면 어떨까? 끝 지점에서 시작지점으로

 

https://leetcode.com/problems/dungeon-game/discuss/52774/C%2B%2B-DP-solution

 

이런 생각을 해볼 수 있다.

시작 지점으로부터 계속 피가 깎여서, 끝 지점으로 왔을때 피가 딱 1이 되도록 하면 그게 답 아닐까?

그럼, 아예 반대로 끝에서 HP=1로 세팅해두고, 시작점으로 올라가면서 답을 찾을 수 있지 않을까?

 

DP[i][j] = 끝 지점에 HP=1로 도달하기 위해, (i,j) 지점에서 최소한도로 가지고 있어야 하는 HP

 

근데, 이 녀석의 점화식이 좀 골때린다.

 

HP_needed = min(DP[i+1][j], DP[i][j+1]) - board[i][j]

DP[i][j] = HP_needed <= 0 ? 1 : HP_needed

 

'- board[i][j]'는 우리가 아래에서 위로 역순으로 이동하니까, 원래는 더해줘야 하는 값이므로 빼주는거지. 이해 완료.

근데 왜 HP_needed가 <= 0 일때 최소 HP를 1로 셋팅해주는거지??

 

잘 생각해보자.

DP 값에서 board 값을 빼서 (= HP_needed) 음수가 나온다는건, board값이 양수였다는 뜻이다.

즉, 원래대로라면 힐링포션을 먹어서 HP가 회복되는 상황이다.

HP_needed가 음수라는 뜻은, 이 칸에서 힐링포션을 먹어서 회복한 HP만으로도, 다음 칸의 공격을 버틸 수 있다는 뜻이다 (우리는 지금 역순으로 올라가고 있으므로, 다음 칸의 상황을 알고 있다!)

따라서, 해당 칸에서 HP는 1만 있어도, 힐링 포션을 먹고 다음 칸까지 버틸 수 있게 되는 것.

 

반대로, board값이 음수인 경우, HP_needed가 양수가 될 수 밖에 없다.

이 경우, 정확히 (i, j)칸의 공격을 버티기 위해 필요한 최소 HP라고 해석할 수 있다.

 

깔끔한 DP 답게, 식도 깔끔하다.

class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int M = dungeon.size();
        int N = dungeon[0].size();
        // hp[i][j] represents the min hp needed at position (i, j)
        // Add dummy row and column at bottom and right side
        vector<vector<int> > hp(M + 1, vector<int>(N + 1, INT_MAX));
        hp[M][N - 1] = 1;
        hp[M - 1][N] = 1;
        for (int i = M - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                int need = min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
                hp[i][j] = need <= 0 ? 1 : need;
            }
        }
        return hp[0][0];
    }
};

 

 

진짜 백지 상태에서 이런 아이디어를 떠올리긴 쉽지 않을 것이다. 

꾸준히 공부하고 기록해서 다양한 패턴을 체화시켜야겠다.