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를 얻습니다. 이제 3 옆에 있는 2는 1 × 2 × 3 = 6을 얻고, 3은 3을 얻습니다. 총 33입니다.
- 입력
- nums = [6, 1, 2, 5]
- 출력
- 108
- 설명
- 1을 곱하고(6 × 1 × 2 = 12), 그다음 2를 곱합니다. 이제 6과 5 사이에 있으므로(6 × 2 × 5 = 60), 그다음 5를 곱해 30, 6을 곱해 6이 됩니다. 모두 합쳐 108입니다.
- 입력
- nums = [8]
- 출력
- 8
- 설명
- 유일한 풍선에는 이웃이 없고, 없는 이웃 하나당 1로 계산되므로 1 × 8 × 1 = 8점을 얻습니다.
후속 질문
가장 많은 코인을 얻는 버스팅 순서도 하나 반환해 주실 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 풍선을 먼저 터뜨릴지 결정한다고 가정해 봅시다. 그러면 양쪽 이웃 풍선들이 서로 인접하게 되어, 왼쪽 풍선들과 오른쪽 풍선들은 여전히 서로 영향을 줍니다. 이런 식으로 문제를 두 개의 더 작은 문제로 나눌 수 있을까요?
질문을 반대로 생각해 보고, 구간에서 마지막으로 터지는 풍선을 고르세요. 그때까지는 벽처럼 그대로 서 있으므로, 왼쪽과 오른쪽에 있는 풍선들은 서로 이웃이 되지 않습니다. 그 풍선이 마침내 터지면, 이웃은 해당 구간의 양쪽 경계에 있는 두 풍선입니다.
nums의 양 끝에 1을 넣으세요.best[left][right]를 위치left와right사이에 엄밀히 놓인 풍선들에서 얻을 수 있는 최대 동전 수라고 합시다. 두 위치 사이의 모든 풍선k를 마지막으로 터뜨릴 풍선으로 시도하세요. 그러면best[left][k] + best[k][right]에vals[left] × vals[k] × vals[right]를 더한 만큼의 동전을 얻습니다. 짧은 간격부터 긴 간격 순으로 채우세요.
풀이
풍선을 하나 터뜨릴 때마다 서로 이웃한 풍선이 달라지므로, 처음 터뜨린 풍선은 줄을 나누지 않습니다. 그 풍선의 양쪽에 있던 풍선이 이웃이 됩니다. 일정 구간에서 마지막으로 터뜨린 풍선은 줄을 나눕니다. 나머지가 모두 사라져도 그 풍선은 남아 있으므로, 양쪽 구간은 서로 독립적이며 구간에 대한 구간 테이블을 사용하면 O(n³)에 문제를 해결할 수 있습니다.
모든 폭발 순서를 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
풍선 하나를 고르고 left × value × right를 계산한 다음, 풍선을 제거하고 같은 방식으로 더 짧아진 행을 풀면서 모든 선택에서 가장 좋은 총합을 유지합니다. 모든 순서를 시도하므로 정확합니다.
첫 번째로 터뜨릴 풍선은 n개 중에서 고르고, 다음은 n-1개 중에서 고르는 식입니다. 순서는 총 n!개이며, 풍선이 12개이면 이미 479,001,600개입니다. 남아 있는 풍선 집합별로 결과를 기억해도 도움이 되지 않습니다. 집합이 2^n개이기 때문입니다.
알고리즘
burstAll(row)을 작성하세요.row의 풍선에서 얻을 수 있는 최대 코인 수를 반환하고, 행이 비어 있으면 0을 반환합니다.- 각 위치
k에 대해, 양쪽 끝을 벗어난 경우 1을 사용하여left × row[k] × right를 얻고,row[k]를 제거한 행에 대해burstAll을 호출한 결과를 더합니다. - 모든
k에 대해 가장 큰 합계를 반환하고,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]. 패딩은 터지지 않으며 빠진 이웃을 대신합니다. solve(left, right)를 서 있는 두 위치 사이에 있는 풍선들로 얻을 수 있는 최대 코인 수라고 합시다.
그 틈에서 k가 마지막으로 터진다고 해 봅시다. 그 안의 다른 모든 풍선은 k가 벽처럼 서 있는 동안 터지므로, left와 k 사이의 부분에는 그 안의 풍선과 양쪽의 고정된 경계만 남고, k와 right 사이의 부분도 마찬가지입니다. k가 터질 때 이웃은 정확히 left와 right입니다. 따라서 이 틈에서 얻을 수 있는 최댓값은 모든 k에 대해 두 부분의 최댓값에 vals[left] × vals[k] × vals[right]를 더한 값 중 가장 큰 값입니다. 정답은 두 패딩 사이의 틈입니다. 틈은 약 n²/2개이고, 각각 최대 n개의 풍선을 시도하므로 메모이제이션을 사용하면 O(n³)이 됩니다.
알고리즘
nums의 양쪽 끝에 1을 추가하여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][k]와 best[k][right]는 이미 최종 값이 됩니다.
[2, 4, 3]을 [1, 2, 4, 3, 1]로 패딩한 경우, best[0][4]는 각 풍선을 마지막에 터뜨리는 경우를 시도합니다. 3을 마지막에 터뜨리면 best[0][3] = 30에 1 × 3 × 1을 더해 33이 되며, 세 경우 중 가장 좋습니다.
작업량은 메모이제이션 버전과 같지만, 일반 루프는 수백만 번의 함수 호출을 건너뛰므로 Python이나 R 같은 언어에서 이 버전은 몇 배 더 빠릅니다.
알고리즘
- 양쪽 끝에 1을 추가한
nums로vals를 만들고,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]
함정과 경계 사례
- 원래 이웃을 기준으로 첫 번째 풍선을 터뜨리고,
nums[k-1] × nums[k] × nums[k+1]에 양쪽 구간의 값을 더합니다. 이 이웃들은 이미 사라졌을 수도 있습니다.[2, 4, 3]에서는 44를 반환하는데, 이는 실제 어떤 순서로 터뜨려도 얻을 수 있는 값보다 큽니다. left를 증가시키면서 표를 행별로 채웁니다. 그러면k > left인best[k][right]는 아직 계산되지 않아 0으로 읽힙니다. 너비 순서대로 채우거나left를 감소시키며 진행하세요.- 메모에서 아직 풀지 않은 구간을 0으로 표시합니다. 값이 0인 풍선으로 이루어진 구간의 실제 값도 0이므로, 방문할 때마다 다시 계산됩니다. -1을 사용하세요.
- Lua와 R에서는 패딩된 위치가 1부터
m까지이므로, 답은best[1][m]입니다.
자주 묻는 질문3
왜 Burst Balloons는 첫 번째 풍선 대신 마지막 풍선을 선택하나요?
첫 번째 폭발 후 양쪽이 이웃이 되므로 서로 계속 영향을 줍니다. 구간의 마지막 풍선은 나머지 풍선들이 터지는 동안 남아 있으므로, 양쪽이 절대 만나지 않으며 각각 독립적인 하위 문제가 됩니다. 마지막 풍선이 터지면 이웃들이 해당 구간의 경계가 됩니다.
풍선 터뜨리기의 시간 복잡도는 얼마인가요?
시간은 O(n³), 메모리는 O(n²)입니다. 간격은 약 n²/2개이고, 각 간격마다 마지막 풍선으로 최대 n개의 풍선을 시도합니다. 풍선이 300개일 때 약 4.5 × 10^6단계입니다. 모든 순서를 시도하면 O(n · n!)입니다.
풍선 터뜨리기 문제를 그리디 순서로 풀 수 있을까요?
아니요. 가장 작은 풍선을 먼저 터뜨리면 [2, 4, 3]에서 24를 얻지만, 33을 얻을 수 있습니다. 지금 가장 큰 금액을 주는 풍선을 터뜨리면 [2, 9, 2]에서 42를 얻지만, 2를 먼저 터뜨리면 18 + 18 + 9 = 45를 얻습니다. 풍선을 터뜨릴 때마다 나중에 터뜨릴 풍선의 가격이 바뀝니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def maxCoins(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
nums = [2, 4, 3]
예상 출력
33