Burst Balloons
풍선이 한 줄로 주어지며, 이를 nums라고 합니다. 여기서 nums[i]는 풍선 i에 적힌 숫자입니다. 원하는 순서대로 풍선을 하나씩 모두 터뜨립니다. 풍선을 터뜨리면 left × nums[i] × right개의 동전을 얻습니다. 여기서 left와 right는 현재 풍선의 이웃, 즉 아직 줄에 남아 있는 양쪽에서 가장 가까운 풍선에 적힌 숫자입니다. 줄의 양 끝 바깥에 있어 이웃이 없는 경우에는 1로 계산합니다. 풍선을 터뜨리고 나면 양쪽 이웃은 서로 인접하게 됩니다. 얻을 수 있는 동전의 최댓값을 반환하세요.
함수
- numsinteger-array
- 풍선에 적힌 숫자, 왼쪽에서 오른쪽 순서로
- 반환값integer
- 모든 풍선을 터뜨려 모을 수 있는 최대 코인 수
제약 조건
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- 정답은 3 × 108보다 작으므로 32비트 부호 있는 정수에 들어갑니다.
예제
- 입력
- nums = [2, 4, 3]
- 출력
- 33
- 설명
- 처음의 4를 터뜨리면 2 × 4 × 3 = 24개의 동전을 얻습니다. 이제 2와 3은 이웃이므로, 2를 터뜨리면 1 × 2 × 3 = 6개를 얻고, 이제 혼자 남은 3을 터뜨리면 1 × 3 × 1 = 3개를 얻습니다. 합계는 33이며, 다른 순서로는 더 높은 점수를 얻을 수 없습니다. 작은 수인 2를 먼저 터뜨리면 얻을 수 있는 점수는 이미 최대 24로 제한됩니다.
- 입력
- nums = [6, 1, 2, 5]
- 출력
- 108
- 설명
- 1을 터뜨리고 (6 × 1 × 2 = 12), 다음으로 2를 터뜨립니다. 이제 6과 5 사이에 있는 2입니다 (6 × 2 × 5 = 60). 그런 다음 5를 터뜨리고 (6 × 5 × 1 = 30), 마지막으로 6을 터뜨립니다 (1 × 6 × 1 = 6). 합계는 12 + 60 + 30 + 6 = 108입니다.
- 입력
- nums = [8]
- 출력
- 8
- 설명
- 유일한 풍선에는 이웃이 없고, 없는 이웃은 각각 1로 계산되므로 1 × 8 × 1 = 8점을 얻습니다.
제출 시 숨은 테스트 +15개
후속 질문
코인을 가장 많이 얻을 수 있는 폭발 순서도 하나 반환해 주실 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 풍선을 먼저 터뜨릴지 정한다고 해 봅시다. 그 풍선의 양옆 풍선들이 서로 이웃하게 되므로, 왼쪽 풍선들과 오른쪽 풍선들은 여전히 서로에게 영향을 줍니다. 이런 방식으로 문제를 두 개의 더 작은 문제로 나눌 수 있을까요?
질문의 관점을 바꿔 한 구간에서 마지막으로 터지는 풍선을 고르세요. 그때까지 그 풍선은 벽처럼 그대로 서 있으므로, 왼쪽에 있는 풍선과 오른쪽에 있는 풍선은 서로 이웃하게 되지 않습니다. 마침내 그 풍선이 터지면, 그 이웃은 구간의 양 끝에 있는 두 풍선입니다.
nums의 양 끝에 1을 넣습니다.best[left][right]를 위치left와right사이에 있는 풍선들에서 얻을 수 있는 최대 코인 수라고 합시다. 그 사이의 모든 풍선k를 마지막으로 터뜨리는 경우로 시도합니다. 이때 얻는 코인 수는best[left][k] + best[k][right]에vals[left] × vals[k] × vals[right]를 더한 값입니다. 짧은 간격부터 긴 간격 순으로 채웁니다.
풀이
각 폭발은 누가 누구 옆에 있게 되는지를 바꾸므로, 지금의 선택은 이후 모든 폭발의 비용을 바꿉니다. 모든 순서를 시도하면 n!개의 순열이 필요합니다. 처음 터지는 풍선을 생각해도 행이 분할되지는 않습니다. 그 풍선의 양쪽이 이웃이 되기 때문입니다. 대신 구간에서 마지막으로 터지는 풍선을 생각하면 됩니다. 그 풍선은 다른 풍선이 모두 사라지는 동안 제자리에 남으므로, 그 왼쪽 구간과 오른쪽 구간은 서로 독립적입니다. 이 구간들을 대상으로 하는 구간 테이블을 사용하면 O(n³)의 시간 복잡도로 문제를 해결할 수 있습니다.
모든 폭발 순서를 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
지금 터뜨릴 풍선을 하나 고르고, 현재 이웃한 풍선들과 함께 left × value × right를 얻은 다음, 그 풍선을 줄에서 제거하고 같은 방식으로 더 짧아진 줄을 해결하세요. 가능한 모든 선택에 대해 이 과정을 수행하고 총점이 가장 높은 값을 유지하세요. 재귀 함수 burstAll(row)가 바로 이 일을 합니다. 가능한 모든 순서를 탐색하므로 정답을 구할 수 있습니다.
하지만 실제 크기의 입력에는 도저히 사용할 수 없습니다. 첫 번째로 터뜨릴 풍선은 n개 중에서 고를 수 있고, 두 번째는 n-1개 중에서 고를 수 있는 식으로 이어집니다. 가능한 순서는 n!개입니다. 풍선이 12개만 있어도 순서가 이미 479,001,600개이고, 가장 큰 테스트에는 풍선이 120개 있습니다. 아직 남아 있는 풍선 집합마다 결과를 기억해도 해결되지 않습니다. 그런 집합이 2^n개나 있기 때문입니다.
이 문제를 해결하려면 하위 문제의 수가 왜 이렇게 많은지 살펴봐야 합니다. 풍선 k를 터뜨리고 나면 왼쪽 풍선과 오른쪽 풍선이 맞닿으므로, 왼쪽에서 일어나는 일은 여전히 오른쪽에 따라 달라집니다. 다음 접근법은 두 쪽이 서로 영향을 주지 않도록 고려할 풍선을 선택합니다.
알고리즘
burstAll(row)를 작성하세요.row에 있는 풍선에서 얻을 수 있는 최대 코인 수를 반환합니다.- 각 위치
k에 대해 양 끝 너머의 값으로 1을 사용하여 이웃을 읽으세요. left × row[k] × right를 얻고,row[k]가 없는 행에 대해burstAll을 더하세요.- 모든
k에 대한 최댓값을 반환하거나, 행이 비어 있으면 0을 반환하세요. burstAll(nums)를 호출하세요.
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)메모를 사용한 마지막 풍선 재귀
핵심 아이디어
먼저 양 끝에 1을 넣습니다: vals = [1] + nums + [1]. 이 둘은 절대 터지지 않으며, 가장자리에 빠져 있는 이웃을 나타냅니다. 이제 여전히 남아 있는 두 위치 left와 right 사이의 간격을 살펴보고, 그 간격 안의 풍선 중 어느 것이 마지막에 터지는지 생각해 보세요.
그 풍선을 k라고 해 봅시다. 간격 안의 다른 풍선들이 터지는 동안 k는 계속 남아 벽처럼 그 사이에 서 있습니다. left와 k 사이에 있는 각 풍선의 이웃은 left와 k를 고정된 경계로 하는 그 구간 안에만 있으며, k와 right 사이도 마찬가지입니다. 따라서 두 구간은 같은 유형의 독립적인 문제입니다. 마침내 k가 터질 때는 경계 사이의 모든 것이 사라졌으므로, 이웃은 정확히 left와 right가 되고 vals[left] × vals[k] × vals[right]만큼의 코인을 얻습니다. 첫 번째 풍선을 선택하면 양쪽이 서로 이웃이 되므로 이런 식으로 나뉘지 않습니다.
이렇게 해서 재귀 관계를 얻습니다. solve(left, right)는 left와 right 사이에 있는 풍선들에서 얻을 수 있는 최대 코인을 반환합니다. 간격이 비어 있으면 0을 반환하고, 그렇지 않으면 간격 안의 모든 k에 대해 solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]를 계산한 값 중 최댓값을 반환합니다. 답은 두 패드 사이의 간격인 solve(0, m-1)입니다.
재귀만 사용하면 같은 간격을 계속해서 다시 계산하게 되므로, 각 결과를 memo[left][right] 테이블에 저장하고 다음에 방문할 때 반환합니다. 간격은 대략 n²/2개이고, 각 간격에서 최대 n개의 풍선을 시도하므로 작업량은 O(n³)입니다. 아직 풀지 않은 간격에는 -1을 사용하세요. 0은 실제 답이 될 수 있기 때문입니다. 각 호출이 더 좁은 간격을 다루므로 재귀 깊이는 최대 n+1번의 호출입니다.
알고리즘
- 양 끝에 1을 추가한
nums로vals를 만들고,m을 길이로 설정합니다. - -1로 채워진
m × m메모를 만듭니다. solve(left, right)를 작성합니다.right - left < 2이면 0을 반환하고, 저장된 값이 있으면 그 값을 반환합니다.- 그렇지 않으면 두 인덱스 사이에 있는 모든
k를 마지막 풍선으로 시도하고,solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]중 가장 큰 값을 유지한 뒤 저장합니다. solve(0, m-1)을 반환합니다.
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)너비별 구간 표 채우기
핵심 아이디어
재귀는 더 좁은 간격만 묻습니다. 따라서 좁은 간격부터 넓은 간격 순으로 채우기만 하면 재귀 없이도 같은 표를 채울 수 있습니다. best[left][right]를 left와 right 사이에 엄밀히 놓인 풍선에서 얻을 수 있는 최대 코인 수라고 하겠습니다. 그 사이에 아무것도 없는 간격의 값은 0입니다. 너비가 2인 경우부터 시작해 너비별로 각 간격을 살펴보고, 그 안의 각 k를 마지막 풍선으로 시도합니다. best[left][k]와 best[k][right]는 더 좁은 간격이므로 이미 최종 값이 정해져 있습니다.
[2, 4, 3]을 살펴보겠습니다. 패딩을 추가하면 위치 0부터 4까지 vals = [1, 2, 4, 3, 1]이 되며, 답은 best[0][4]입니다. 가장 좁은 간격부터 채웁니다.
- 너비 2, 안에 풍선이 하나 있는 경우:
best[0][2] = 1 × 2 × 4 = 8,best[1][3] = 2 × 4 × 3 = 24,best[2][4] = 4 × 3 × 1 = 12. best[0][3], 풍선 2와 4: 2를 마지막으로 터뜨리면0 + 24 + 1 × 2 × 3 = 30이고, 4를 마지막으로 터뜨리면8 + 0 + 1 × 4 × 3 = 20입니다. 따라서 30입니다.best[1][4], 풍선 4와 3: 4를 마지막으로 터뜨리면0 + 12 + 2 × 4 × 1 = 20이고, 3을 마지막으로 터뜨리면24 + 0 + 2 × 3 × 1 = 30입니다. 따라서 30입니다.best[0][4], 풍선 세 개 모두: 2를 마지막으로 터뜨리면0 + 30 + 1 × 2 × 1 = 32이고, 4를 마지막으로 터뜨리면8 + 12 + 1 × 4 × 1 = 24이며, 3을 마지막으로 터뜨리면30 + 0 + 1 × 3 × 1 = 33입니다. 따라서 33입니다.
가장 좋은 선택을 거꾸로 따라가면 순서를 알 수 있습니다. 3이 마지막에 터지고, 그 전에 왼쪽 구간에서는 2가 마지막에 터지며, 4가 처음에 터집니다. 즉, 24 + 6 + 3 = 33입니다.
계산량은 메모이제이션을 사용한 경우와 같습니다. 풍선 300개라면 302 × 301 × 300 / 6 ≈ 4.5 × 10^6단계이고, 302 × 302개의 숫자로 이루어진 표가 필요합니다. 단순한 반복문을 사용하면 수백만 번의 함수 호출을 피할 수 있으므로, Python이나 R 같은 언어에서는 이 방식이 재귀보다 몇 배 더 빠릅니다.
알고리즘
vals를 양쪽 끝에 각각 1을 추가한nums로 만들고,m을 그 길이로 설정합니다.- 0으로 채운
m × m표best를 만듭니다. - 너비를 2부터
m-1까지 늘려 가며, 배열 안에서right = left + width인 각left에 대해, 그 사이에 있는 모든k를 시도합니다. best[left][right]를best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]중 가장 큰 값으로 설정합니다.best[0][m-1]을 반환합니다.
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
함정과 경계 사례
흔한 실수로는 그리디 순서 선택, 첫 번째 풍선을 터뜨리는 방식의 재귀, 잘못된 메모이제이션 표식, 잘못된 순서로 표 채우기 등이 있습니다.
- 그리디 순서는 실패합니다. 가장 작은 풍선을 먼저 터뜨리면
[2, 4, 3]에서 24를 얻지만 33을 얻지는 못하고, 당장 가장 큰 값을 주는 풍선을 터뜨리면[2, 9, 2]에서 42를 얻습니다. 반면 2를 먼저 터뜨리면 18 + 18 + 9 = 45를 얻습니다. - 원래 이웃을 기준으로 첫 번째로 터뜨릴 풍선을 정하고,
nums[k-1] × nums[k] × nums[k+1]에 양쪽 구간의 값을 더하면 이미 사라졌을 수도 있는 이웃을 계산에 포함하게 됩니다.[2, 4, 3]에서는 44를 반환하는데, 이는 실제 어떤 순서로 터뜨려도 얻을 수 있는 값보다 큽니다. - 경계 풍선을 구간에 포함해 계산하는 실수입니다. 구간을 비울 때
left와right는 여전히 남아 있습니다. 두 풍선 사이에 있는 풍선만 터뜨립니다. left를 증가시키면서 표를 행별로 채우는 실수입니다. 그러면k > left일 때best[k][right]가 아직 계산되지 않아 0으로 읽힙니다. 너비 순서대로 채우거나left를 내림차순으로 순회하세요.- 아직 풀지 않은 구간을 메모이제이션 표에서 0으로 표시하는 실수입니다. 풍선이 0개인 구간의 값도 실제로 0이므로, 계속 미해결 상태처럼 보여 방문할 때마다 다시 풉니다. -1을 사용하세요.
- 양쪽에 채워 넣은 1 두 개를 잊으면 양 끝 풍선에 곱할 이웃이 없어집니다.
- Lua와 R에서는 채워 넣은 위치가 1부터
m까지이므로, 답은best[1][m]입니다.
자주 묻는 질문4
왜 Burst Balloons는 첫 번째 풍선 대신 마지막 풍선을 선택하나요?
첫 번째로 풍선을 터뜨리고 나면 양쪽의 풍선들이 이웃하게 되므로, 왼쪽 부분과 오른쪽 부분은 여전히 서로 영향을 주며 따로 해결할 수 없습니다. 한 구간의 마지막 풍선은 나머지 풍선들이 터지는 동안 제자리에 남아 있으므로 양쪽은 절대 만나지 않으며, 그 풍선을 터뜨릴 때 이웃한 풍선들은 해당 구간의 고정된 경계가 됩니다. 따라서 각 구간은 독립적인 하위 문제가 되며, 이것이 동적 프로그래밍에 필요한 조건입니다.
풍선 터뜨리기의 시간 복잡도는 얼마인가요?
구간 테이블에는 약 n²/2개의 간격이 있고, 각 간격은 최대 n개의 풍선을 마지막 풍선으로 시도하므로 시간 복잡도는 O(n³), 메모리 복잡도는 O(n²)입니다. 풍선이 300개라면 약 4.5 × 10^6단계입니다. 모든 순서를 시도하면 O(n · n!)입니다.
풍선 터뜨리기 문제를 그리디 순서로 풀 수 있을까요?
아니요. 모든 단순한 규칙은 작은 배열에서 실패합니다. 가장 작은 풍선을 먼저 터뜨리면 [2, 4, 3]에서 24를 얻지만, 가능한 최댓값은 33입니다. 당장 가장 많은 값을 주는 풍선을 터뜨리면 [2, 9, 2]에서 42를 얻지만, 2를 먼저 터뜨리면 45를 얻습니다. 풍선을 터뜨리면 나중 풍선의 가격이 바뀌므로, 간격에 대한 동적 계획법이 필요합니다.
배열의 양쪽 끝에 1을 추가하는 이유는 무엇인가요?
이웃이 없으면 1로 계산하므로, 터지지 않는 값이 1인 패딩 풍선 두 개가 모든 실제 풍선에 별도 예외 처리 없이 두 이웃을 제공합니다. 또한 이들은 문제 전체의 경계 역할도 합니다. 정답은 두 패딩 사이의 간격인 best[0][m-1]입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def maxCoins(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [2, 4, 3]
기대값
33