(H312 - Burst Balloons) DP 이전정보 + reverse thinking

배울점 

- 이전 정보를 정의에 포함 (H546 - Remove Boxes 연장선)

- DP 정의가 틀렸음을 느끼는 순간

- Reverse thinking

 

 

i번째 풍선 선택 시, nums[i - 1] * nums[i] * nums[i + 1] 의 점수를 얻을 수 있다.

최대 점수를 얻도록 풍선을 터뜨리는 방법은?

 

 

[i...j] 범위의 중간 풍선인 k를 제거하면 배열이 둘로 쪼개진다.

나뉘어진 부분을 각각 재귀적으로 푼 다음 합치면 어떨까? (Divide-and-Conquer)

 

 

❗ 문제를 푸는데 있어서 양 옆 끝 숫자의 정보가 필요하다 (left, right).

예를 들어 dp(i, k-1)에서 맨 오른쪽 끝 풍선을 제거하면 'nums[k+1]'을 곱해줘야 하는데, dp 입장에서는 이를 알 수 없다

(DP정의에 포함되지 않는 정보, 이전 정보; not self-contained)

✅ 이전 정보를 정의에 포함시키자

 

❗❗ 또 다른 문제가 생기는데, 답을 결정하는 Parameter가 4개가 되니까, int memo[MAXN][MAXN][MAXN][MAXN] 같이 4차원 배열이 필요함. MAXN = 501이니까, 250GB라는 어마어마한 메모리가 필요함.

✅ map을 활용. Parameter를 pair, string등으로 인코딩하려고 해보자

 

❗❗❗ 또, left, right 때문에 중복되는 문제 많이 안생김

→ 이쯤되면 문제 정의가 잘못된 것. 다른 정의를 찾아야 함.

 

나중에 가서 보니, 이 정의는 틀린 풀이인데, k를 골라서 배열을 둘로 나누어도 나중에 저 두 배열이 서로의 정보를 필요로 하는 상황이 올 수 있기 때문

ex) [3,1,5,8] 에서, 맨 처음에 1을 없애서 3 / 5 8 로 나뉘어도
맨 마지막에는 [3, 8] 로 다시 합쳐져서 무조건 3을 먼저 없애야 함.
∴ 깔끔하게 3 / 5 8 로 나눠서 해결한 다음 두 결과를 합치는게 불가능.

 

 

---

난 여기서 고민하다가 포기하고 다음 해설을 봤다.

https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

 

💡 핵심 : 첫번째로 없앨 풍선을 선택하는게 아니라, 마지막으로 없앨 풍선을 선택하는 것 (reverse thinking)

왜? 마지막으로 없애면, 그 풍선을 기점으로 둘로 나뉘어지는 배열은 서로 서로가 전혀 연관이 없음

(위에서 언급했던 문제점 해결)

⭐ 또 이 정의를 선택하면, left right는 항상 nums[i-1], nums[j+1]이 되므로 파라미터에 포함시키지 않아도 됨.

int memo[MAXN][MAXN]; 메모이제이션으로도 충분!