Split Array Largest Sum
음이 아닌 정수 배열 nums와 정수 k가 주어집니다. nums를 정확히 k개의 부분으로 나누세요. 각 부분은 비어 있지 않은 인접한 값들의 연속 구간이어야 하며, 부분들의 순서는 유지되어야 합니다. 각 부분에는 합이 있으며, 분할의 비용은 각 부분 합 중 가장 큰 값입니다.
k개의 부분으로 나누었을 때 얻을 수 있는 가장 작은 비용을 반환하세요.
함수
- numsinteger-array
- 음수가 아닌 값들을 순서대로
- kinteger
- 잘라서 만들 연속된 부분의 개수
- 반환값integer
- 가장 큰 부분 합의 가능한 최솟값
제약 조건
1 ≤ nums.length ≤ 50000 ≤ nums[i] ≤ 1051 ≤ k ≤ nums.length- 각 부분에는 값이 하나 이상 들어 있습니다. 모든 값이 0인 부분의 합은 0이며, 이는 허용됩니다.
예제
- 입력
- nums = [6, 2, 9, 4, 7, 3]k = 3
- 출력
- 13
- 설명
[6, 2],[9, 4],[7, 3]으로 나누면 비용은 13입니다. 어떤 방식으로도 나누지 않으면 비용은 12입니다. 12 이하가 되도록 왼쪽에서 오른쪽으로 부품을 묶으면[6, 2],[9],[4, 7],[3]으로, 네 부분이 됩니다.
- 입력
- nums = [8, 1, 1, 1, 5]k = 2
- 출력
- 8
- 설명
- 8은 어느 한 부분에 들어 있으므로, 어떤 분할도 8보다 적은 비용이 들 수 없습니다.
[8]과[1, 1, 1, 5]는 모두 합이 8입니다.
- 입력
- nums = [3, 0, 4]k = 3
- 출력
- 4
- 설명
- 값이 3개이고 부분도 3개이므로 각 부분에 값이 하나씩 남으며, 합계는 3, 0, 4입니다. 합계가 0인 부분도 허용됩니다.
후속 질문
누적 합을 사용하면 탐욕적 검사를 통해 이분 탐색으로 각 부분이 끝나는 위치를 찾을 수 있습니다. k가 작을 때 전체 방법은 얼마나 빨라질까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
가장 큰 부분의 합이 최대
c일 수 있다고 누군가 약속한다고 가정해 봅시다.k개의 부분이면 충분한지 빠르게 판단할 수 있나요?부분을 왼쪽에서 오른쪽으로 채우고, 다음 값을 추가하면
c를 초과할 때만 부분을 닫으세요. 그러면 부분의 개수가 최소가 되며,c가 더 커져도 필요한 부분의 개수가 늘어나지는 않습니다.최댓값과 총합 사이에서
c를 이진 탐색합니다. 그리디 방식으로 계산한 개수가k이하라면 답은c이하이고, 그렇지 않으면 더 큽니다.
풀이
동적 프로그래밍을 사용하더라도 최적의 분할을 직접 찾으려면 O(k·n²)의 비용이 듭니다. 질문을 뒤집어 생각해 보세요. k개의 부분이 주어진 상한을 넘지 않게 할 수 있을까요? 그 질문에는 한 번의 탐욕적 순회로 답할 수 있고, 상한이 커짐에 따라 답은 한 번만 아니요에서 예로 바뀌며, 이 경계는 이분 탐색으로 찾을 수 있습니다.
접두사에 대한 동적 계획법
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
best[p][j]를 처음 j개의 값을 p개의 부분으로 나눌 때의 최소 비용이라고 하자. 마지막 부분이 nums[i..j-1]이면 비용은 best[p-1][i]와 그 부분의 합 중 큰 값이며, 처음 i개의 값에 대한 최적 분할은 그 오른쪽에 있는 어떤 것에도 영향을 받지 않는다. 따라서 best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i])이며, 모든 부분에 값이 하나씩 포함되도록 i의 범위는 p-1부터 j-1까지다. 행 p는 행 p-1만 참조하므로 행 두 개면 충분하다.
최대 k·n²/2번의 연산이 실행된다. n = 5000, k = 2500일 때 약 1.8 × 10^10번이다.
알고리즘
prefix를 구성합니다. 여기서prefix[j]는 처음j개 값의 합이며, 한 부분으로 나누는 경우best[j] = prefix[j]로 설정합니다.- 부분의 개수
p를 2부터k까지, 각 끝 위치j를p부터n까지 순회하며,p-1부터j-1까지의i에 대해max(best[i], prefix[j] - prefix[i])의 최솟값을 구합니다. - 그 최솟값들을 새 행에 저장하고, 해당 행을
best로 설정합니다. best[n]을 반환합니다.
def splitArray(nums, k):
n = len(nums)
# prefix[j] is the sum of the first j values
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
# best[j]: the smallest largest part when the first j values form one part
best = prefix[:]
for parts in range(2, k + 1):
nxt = [0] * (n + 1)
for j in range(parts, n + 1):
lowest = prefix[j] # never worse than one part holding everything
for i in range(parts - 1, j):
# the first i values form parts-1 parts, nums[i..j-1] is the last part
worst = max(best[i], prefix[j] - prefix[i])
if worst < lowest:
lowest = worst
nxt[j] = lowest
best = nxt
return best[n]최대 합에 대한 이진 탐색
핵심 아이디어
상한값 c를 테스트하려면 왼쪽에서 오른쪽으로 훑으면서 현재 구간의 합이 c를 넘지 않는 동안 값을 더한 다음, 새 구간을 시작합니다. 이렇게 하면 가능한 구간 수가 최소가 됩니다. 어떤 유효한 분할과 비교해도 그리디 방식의 첫 번째 구간은 적어도 같은 위치까지 이어지므로, 다음 구간은 다른 분할의 다음 구간보다 같거나 더 뒤에서 시작합니다. 그 구간의 끝까지 그리디 방식으로 선택한 값들은 어떤 구간의 일부이며, 음수가 없으므로 일부의 합은 전체의 합보다 커질 수 없습니다. 따라서 그리디 방식은 결코 뒤처지지 않습니다.
k개보다 적은 구간도 k개인 경우만큼 좋습니다. 값이 두 개 이상인 구간을 둘로 나누어도 합은 절대 커지지 않기 때문입니다. 따라서 테스트 조건은 partsNeeded(c) ≤ k입니다.
max(nums)와 sum(nums) 사이에서 조건을 만족하는 가장 작은 상한값을 이진 탐색합니다. max(nums)는 어떤 구간에 반드시 들어가고, sum(nums)은 항상 하나의 구간에 들어갈 수 있기 때문입니다.
알고리즘
lo = max(nums)와hi = sum(nums)를 설정합니다.lo < hi인 동안mid = lo + (hi - lo) / 2를 구합니다.mid를 기준으로 그리디하게 부분 배열의 개수를 셉니다. 합이 0인 부분 배열 1개로 시작하고, 값을 더했을 때mid를 초과하면 부분 배열을 하나 추가하고 그 값부터 합계를 다시 시작합니다.- 개수가
k이하이면hi = mid로 설정하고, 그렇지 않으면lo = mid + 1로 설정합니다. lo를 반환합니다.
def splitArray(nums, k):
def parts_needed(cap):
# Fill each part left to right and start a new one only when the next value would pass cap.
parts, current = 1, 0
for x in nums:
if current + x > cap:
parts += 1
current = x
else:
current += x
return parts
lo, hi = max(nums), sum(nums) # one value per part at best, everything in one part at worst
while lo < hi:
mid = (lo + hi) // 2
if parts_needed(mid) <= k:
hi = mid # mid works, so the answer is mid or smaller
else:
lo = mid + 1 # mid needs more than k parts, so the answer is larger
return lo
함정과 경계 사례
lo를max(nums)보다 작은 값에서 시작합니다. 그리디 알고리즘은 최댓값을 초과하는 값을 하나의 구간에 따로 배치하므로,k = 2일 때[1, 9]에 대해 상한 5도 괜찮다고 판단합니다.partsNeeded(c) == k인지 테스트합니다.[3, 0, 4]와k = 3의 경우, 상한 4에서는[3, 0],[4]로 묶이므로 어떤 상한도 조건을 만족하지 않습니다.- 구간 수를 0부터 세어 모든 개수가 하나씩 작아집니다.
mid가 조건을 만족할 때hi = mid - 1로 설정하면, 답이mid일 때 답을 놓치게 됩니다.- DP의
i를 0에서 시작합니다. 구간보다 값의 개수가 적은 셀은 비용을 0으로 읽으며,k = 3일 때[100, 1, 1]에 대해 100 대신 2를 반환합니다.
자주 묻는 질문3
배열 분할의 최대 합의 시간 복잡도는 무엇인가요?
O(n log S) 시간 및 O(1) 추가 공간이 필요합니다. 여기서 S는 nums의 합입니다. 각 그리디 검사는 한 번의 순회로 이루어지고, 검사할 때마다 상한 범위가 절반으로 줄어듭니다. S = 5 × 10^8일 때 검사는 약 29회입니다. DP는 O(k·n²) 시간이 걸립니다.
실현 가능성 검사는 왜 단조적인가요?
분할의 각 부분의 합이 모두 최대 c라면, 같은 분할은 c+1 이하에서도 성립합니다. 따라서 어떤 상한이 가능하면 그보다 큰 모든 상한도 가능하고, 답은 no가 이어진 뒤 yes가 이어지는 형태입니다. 이분 탐색으로 첫 번째 yes를 찾습니다.
이진 검색은 음수에서도 작동하나요?
아니요. 음수 값은 합을 낮출 수 있으므로 그리디 방식은 구간을 너무 일찍 닫을 수 있고, 구간을 나누면 한 조각의 값이 전체보다 커질 수 있습니다. DP는 어느 가정도 하지 않으므로 계속 올바르게 작동합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def splitArray(nums, k):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [6, 2, 9, 4, 7, 3] k = 3
예상 출력
13