문제 개요
n개의 풍선이 있으며, 각 풍선에는 0부터 n-1까지 번호가 붙어 있습니다. 각 풍선에는 nums 배열에 담긴 숫자가 하나씩 적혀 있고, 우리는 모든 풍선을 터뜨려야 합니다. i번째 풍선을 터뜨리면 nums[i-1] × nums[i] × nums[i+1]만큼의 코인을 얻게 되며, 풍선이 터진 후에는 i-1번과 i+1번 풍선이 서로 이웃하게 됩니다. 목표는 풍선을 가장 유리한 순서로 터뜨려 모을 수 있는 코인의 최댓값을 구하는 것입니다.
예시로 이해하기
입력이 [3, 1, 5, 7]이라면 정답은 148입니다. 터뜨리는 과정을 하나씩 살펴보겠습니다.
- 처음 배열 상태: [3, 1, 5, 7]
- 1을 터뜨림 → 3 × 1 × 5 = 15코인 획득, 배열은 [3, 5, 7]
- 5를 터뜨림 → 3 × 5 × 7 = 105코인 획득, 배열은 [3, 7]
- 3을 터뜨림 → 1 × 3 × 7 = 21코인 획득, 배열은 [7]
- 마지막으로 7을 터뜨림 → 7코인 획득
따라서 총 획득 코인은 15 + 105 + 21 + 7 = 148입니다.
해결 전략: 동적 계획법(DP)
이 문제는 구간 단위 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '구간 [l, r] 안에서 마지막으로 터뜨릴 풍선을 i라고 가정'하는 것입니다. i가 해당 구간에서 마지막에 터지는 풍선이라면, 그 순간 i의 좌우에는 구간 바깥 경계에 해당하는 a[l-1]과 a[r+1]이 인접해 있습니다. 따라서 i를 터뜨릴 때 얻는 코인은 a[l-1] × a[i] × a[r+1]이 되고, 여기에 왼쪽 부분 구간 [l, i-1]과 오른쪽 부분 구간 [i+1, r]에서 각각 얻을 수 있는 최대 코인(dp[l][i-1]과 dp[i+1][r])을 더해주면 됩니다. 인덱스가 배열 범위를 벗어나는 경우에는 곱셈 항목을 1로, dp 값은 0으로 처리합니다.
알고리즘의 전체 흐름은 다음과 같습니다.
- n := 배열 a의 크기를 구합니다.
- n이 0이면 0을 반환합니다.
- n × n 크기의 2차원 배열 dp를 선언합니다.
- l을 n-1부터 0까지 감소시키며 반복합니다.
- r을 l부터 n-1까지 증가시키며 반복합니다.
- i를 l부터 r까지 증가시키며 반복합니다.
- y := (i+1 < n이면 dp[i+1][r], 아니면 0)
- z := (l-1 ≥ 0이면 a[l-1], 아니면 1)
- w := (r+1 < n이면 a[r+1], 아니면 1)
- x := ((i-1 ≥ 0이면 dp[l][i-1], 아니면 0) + y + z × w × a[i])
- dp[l][r] := dp[l][r]와 x 중 더 큰 값
- i를 l부터 r까지 증가시키며 반복합니다.
- r을 l부터 n-1까지 증가시키며 반복합니다.
- dp[0][n-1]을 반환합니다.
C++ 구현 코드
다음은 위 알고리즘을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxCoins(vector<int>& a) {
int n = a.size();
if(!n) return 0;
vector<vector<int>> dp(n, vector<int>(n));
for(int l = n-1; l >= 0; l--){
for(int r = l; r < n; r++){
for(int i = l; i <= r; i++){
dp[l][r] = max(dp[l][r],
(i-1 >= 0 ? dp[l][i-1] : 0) +
(i+1 < n ? dp[i+1][r] : 0) +
((l-1 >= 0 ? a[l-1] : 1) *
(r+1 < n ? a[r+1] : 1) * a[i]));
}
}
}
return dp[0][n-1];
}
};
main(){
Solution ob;
vector<int> v = {3,1,5,7};
cout << (ob.maxCoins(v));
}실행 결과 확인
입력:
[3,1,5,7]
출력:
148
복잡도 분석
세 겹의 반복문을 사용하므로 시간 복잡도는 O(n³)이며, n × n 크기의 dp 테이블을 사용하므로 공간 복잡도는 O(n²)입니다.