(H546 - Remove Boxes) DP 이전정보 처리하기 ★

배울 점

- 문제를 DP로 해석하기 - 재귀 구조를 만들려는 생각
- 이전 정보를 정의에 포함시켜 처리
- Top-down → Bottom-up

 

문제를 딱 보고 '이걸 DP로 처리할 수 있을까?' 싶었다.

boxes = [1,3,2,2,2,3,4,3,1] 에서, 중간의 '2,2,2'를 처리하면 [1,3,3,4,3,1] 이 되는데, 원래 배열과 모습이 크게 다르지 않은가?

(사실 2,2,2 앞 뒤의 [1,3] 과 [3,4,3,1]을 합쳐서 다시 removeBoxes를 호출하는 방법이 떠올라 구현해봤는데, 조각이 지나치게 많아지면 일일히 해보다가 TLE나서 실패)

 

 

이 사람은 이 문제를 DP로 접근했는데, 논리 과정을 잘 설명해놨다. 읽고 꼭 배우자.

https://leetcode.com/problems/remove-boxes/discuss/101310/Java-top-down-and-bottom-up-DP-solutions

Java top-down and bottom-up DP solutions - LeetCode Discuss

 

---

T(i, j) : boxes[i, j]를 처리했을 때 max point

라고 하자.

 

우린 여기서 복잡하게 생각하지 않고, 첫번째 박스 boxes[i]를 제거하냐 마냐만 생각한다.

 

Case 1. 바로 제거한다

→ T(i, j) = 1 + T(i+1, j)

 

Case 2. boxes[i]와 똑같은 박스들이 뒤에 더 나타날 수 있으므로, 일단 남겨놓고 나중에 처리

→ index 'm'에서 boxes[i]와 같은 박스가 나타났다고 하자.

T(i, j) = T(i + 1, m-1) + (boxes[i]와 boxes[m...j]을 처리해서 얻을 max point)

 

여기서 boxes[m...j]를 처리하는건 T(m, j)로 표현할 수 있는데, boxes[i]라는 이전 정보가 남아있다.

 🚨 현재 T 정의로는 이 이전정보를 T(m, j) 입장에서 알 수가 없다 🚨

(저자는 이렇게 표현 : In this case, I shall call that the definition of the subproblem is not self-contained and its solution relies on information external to the subproblem itself.)

 

 

💡 이미 공부했다시피, 이전 정보가 남아있는 상태에서는 Optimal substructure 구조를 만족할 수 없기에, 문제를 푸는 재귀 구조를 만들 수 없다 (DP의 핵심).

이 문제를 해결하는 방법은, '이전 정보'를 DP 정의에 포함시키는 방법이다.

Problems without self-contained subproblems usually don't have well-defined recurrence relations, which renders it impossible to be solved recursively. The cure to this issue can sound simple and straightforward: 
modify the definition of the problem to absorb the external information so that the new one is self-contained

 

이전 정보를 제대로 파악해보자

T(m, j) 입장에선, 가장 왼쪽의 박스인 boxes[m]과 색깔이 똑같으며 left border를 맞대고 있는 박스의 개수 k가 중요하다. 

(만약 boxes[m]을 없앤다는 결정을 하면, k+1개를 없애게 되는 것이므로)

 

✅ DP문제 정의를 다음과 같이 바꾼다

T(i, j, k) : boxes[i]와 같은 색깔의 박스 k개가 왼쪽편에 붙어있을 때, boxes[i, j]를 처리하고 얻는 max point

 

이후 맨 처음 진행했던 것 처럼 Case분류 해보면, 

Case 1. T(i, j, k) = (k+1) * (k+1) + T(i+1, j, 0)

Case 2. T(i, j, k) = T(i+1, m-1, 0) + T(m, j, k+1)  (boxes[m] == boxes[i])

로 깔끔하게 점화식을 세울 수 있다.

 

// Removes Boxes [i...j] where there were 'k' boxes same as boxes[i] previously
int dp(int i, int j, int k) {
    if (i == j) return (k + 1) * (k + 1);
    else if (j == i - 1) return 0;

    int& ret = memo[i][j][k];
    if (ret != -1) return ret;

    ret = (k + 1) * (k + 1) + dp(i + 1, j, 0); // remove boxes[i] (+ k adjacent)

    // ★ 같은 box가 나오더라도 무조건 합쳐야 하는건 아님. 대의를 위해 당장은 무시할수도
    // [1, 1, 2, 2, 1, 2, 2, 2, 2, 1, 1] 에서 중간에 1을 무시하는 것 처럼
    FOReq(m, i + 1, j) {
        if (box[m] != box[i]) 
            continue;
        ret = max(ret, dp(i + 1, m - 1, 0) + dp(m, j, k + 1)); // keep box[i] until same box appears at 'm'
    }
    return ret;
}

 

---

✏️ Follow-up) Top-down을 Bottom-up으로 다시 짜기

Step 1. 테이블을 채워나갈 방향 정하기.

→ 이 문제의 경우, dp(i, j, k)를 채우기 위해 dp(i + 1, j, 0), dp(i + 1, m - 1, 0) + dp(m, j, k + 1)
등이 필요함. 즉, i와 j를 N-1부터 0까지 역방향으로 채워나가야 함
(k는 0에서 i까지 채워도 상관X)

 

테이블을 직접 그려보면 바로 알 수 있다!

k까지 고려하면, 저 먹다남은 치즈케이크 모양의 파란색을 채워야 함을 알 수 있다

Step 2. Base condition, 점화식 그대로 구현

→ memoization 하는 방식만 바뀐거지, 기본 로직은 그대로임.
Time complexity도 당연히 그대로일 수 밖에 없으니, 구했던 점화식 똑같이 구현해주면 됨.