Split Array Largest Sum

Q: Split Array Largest Sum의 시간 복잡도는 얼마인가요?

이분 탐색은 O(n log S) 시간에 실행됩니다. 여기서 n 은 nums 의 길이이고 S 는 그 합입니다. 각 탐욕적 검사는 배열을 한 번 순회하며, 상한 범위는 검사할 때마다 절반으로 줄어듭니다. S = 5 × 10^8 일 때 약 29번 검사합니다. 추가 공간은 O(1) 을 사용합니다. DP는 O(k·n²) 시간과 O(n) 공간을 사용합니다.

Q: 실현 가능성 검사는 왜 단조적인가요?

어떤 분할의 각 부분의 합이 모두 최대 c 라면, 같은 분할에서 각 부분의 합은 모두 최대 c+1 입니다. 따라서 어떤 상한이 조건을 만족하면 그보다 큰 모든 상한도 조건을 만족하고, 어떤 상한이 조건을 만족하지 않으면 그보다 작은 모든 상한도 조건을 만족하지 않습니다. 답은 ‘아니요’가 이어진 다음 ‘예’가 이어지는 형태이므로, 경계를 찾는 데 필요한 것은 바로 이진 탐색입니다.

Q: 그리디 검사는 왜 부분의 개수가 가장 적은 경우를 찾을까요?

그리디 방식은 다음 값을 더하면 상한을 초과하게 될 때까지 한 부분에 값을 계속 더합니다. 이를 유효한 분할과 부분별로 비교해 보세요. 각 그리디 부분은 같은 번호의 다른 분할 부분이 시작하는 위치와 같거나 그 이후에 시작하므로, 해당 부분의 끝까지 포함하는 값들은 상한 이하인 부분의 일부입니다. 값은 음수가 아니므로 그 조각도 상한 이하이며, 그리디 방식은 적어도 그만큼 더 확장됩니다. 그리디 방식은 결코 뒤처지지 않으므로, 어떤 분할보다도 적은 부분으로 배열 전체를 포함합니다.

Q: 이진 검색은 음수에서도 작동하나요?

아니요. 음수 값이 있으면 값을 더했을 때 합이 작아질 수 있으므로, 그리디 방식은 너무 일찍 한 부분을 닫아 유효한 분할을 놓칠 수 있습니다. 한 부분을 나누면 한 조각의 합이 전체의 합보다 커질 수도 있으므로, 부분이 k 개 미만이라고 해서 k 개 부분으로 분할할 수 있다는 뜻은 더 이상 아닙니다. DP는 어느 가정도 하지 않으므로 O(k·n²) 시간에 올바르게 동작합니다.

어려움이진 탐색 동적 계획법

+10

음수가 아닌 정수로 이루어진 배열 nums와 정수 k가 주어집니다. nums를 정확히 k개의 부분으로 나누세요. 각 부분은 서로 이웃한 값들로 이루어진 비어 있지 않은 연속 구간이어야 하며, 부분들의 순서는 유지해야 합니다. 각 부분에는 합이 있으며, 분할의 비용은 그 합들 중 가장 큰 값입니다.

k개의 부분으로 나누었을 때 도달할 수 있는 가장 작은 비용을 반환하세요.

함수

splitArray(nums: integer-array, k: integer) → integer

numsinteger-array: 음이 아닌 값들을 순서대로
kinteger: 이들을 잘라 나눌 연속된 부분의 수
반환값integer: 가장 큰 부분 합의 가능한 최솟값

제약 조건

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
각 부분은 최소 하나의 값을 포함합니다. 모든 값이 0인 부분의 합은 0이며, 이는 허용됩니다.

예제

입력: nums = [6, 2, 9, 4, 7, 3]k = 3
출력: 13
설명: 분할 [6, 2], [9, 4], [7, 3]의 합은 8, 13, 10이므로 비용은 13입니다. 비용이 12인 분할은 없습니다. 각 합이 12 이하가 되도록 왼쪽에서 오른쪽으로 묶으면 [6, 2], [9], [4, 7], [3]이 되어, 허용된 부분은 3개뿐인데 4개가 됩니다.

입력: nums = [8, 1, 1, 1, 5]k = 2
출력: 8
설명: 8은 일부 구간에 있으므로 어떤 분할도 비용이 8보다 낮을 수 없습니다. [8]과 [1, 1, 1, 5]의 합은 모두 8이므로, 8에 도달합니다.

제출 시 숨은 테스트 +20개

후속 질문

각 탐욕적 검사는 모든 n 값을 읽습니다. 누적 합을 사용하면 검사에서 이진 탐색으로 각 부분이 끝나는 위치를 찾을 수 있습니다. k가 작고 nums가 길 때 전체 방법의 속도는 얼마나 빨라질까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

두 가지 요구사항은 서로 충돌합니다. 정확히 k개의 구간을 사용해야 하고, 가장 큰 구간의 크기는 가능한 한 작아야 합니다. k-1개의 분할 지점을 모두 시도하면 경우의 수가 폭발적으로 늘어나고, 접두 구간을 대상으로 동적 계획법을 사용하면 이를 O(k·n²)까지 줄일 수 있지만, 값이 5000개일 때는 여전히 너무 느립니다. 빠른 방법은 질문을 뒤집는 것입니다. 최적의 분할을 찾는 대신, 상한을 하나 정하고 k개의 구간이 그 상한을 넘지 않게 나눌 수 있는지 확인합니다. 탐욕적으로 한 번 훑으면 답을 구할 수 있고, 상한이 커짐에 따라 답은 한 번만 바뀌므로 이분 탐색으로 약 29번의 탐색 안에 그 지점을 찾을 수 있습니다.

접두사에 대한 동적 프로그래밍

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

분할의 마지막 부분을 살펴보세요. 처음 j개의 값이 p개의 부분을 이룬다면, 마지막 부분은 nums[i..j-1]이라는 연속 구간이고 처음 i개의 값은 나머지 p-1개의 부분을 이룹니다. 비용은 두 값 중 더 큰 값입니다. 하나는 그 p-1개 부분의 비용이고, 다른 하나는 마지막 구간의 합입니다. 마지막 구간이 무엇이든 처음 i개의 값을 가능한 한 낮은 비용으로 분할하고 싶을 것이며, 그 최적 분할은 오른쪽에 있는 값과 무관합니다. 따라서 한 번 계산해 재사용할 수 있습니다.

best[p][j]를 처음 j개의 값을 p개의 부분으로 나눌 때의 최소 비용이라고 하겠습니다. 부분이 하나라면 선택의 여지가 없습니다. best[1][j]는 처음 j개 값의 합입니다. 부분이 더 많다면 마지막 부분의 모든 시작 위치 i를 시도합니다. best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i])이며, 여기서 prefix[j]는 처음 j개 값의 합입니다. p-1개의 비어 있지 않은 부분을 만들려면 값이 최소 p-1개 필요하므로 시작 위치 i는 p-1부터 시작하고, 마지막 부분에도 값이 하나 필요하므로 j-1까지입니다. 정답은 best[k][n]입니다. 행 p는 행 p-1만 참조하므로 길이가 n+1인 행 두 개면 충분합니다.

첫 번째 예시에서 [6, 2, 9, 4]를 두 부분으로 나눌 때 첫 번째 부분을 6 뒤에서 끝내면 비용은 max(6, 15) = 15이고, 2 뒤에서 끝내면 max(8, 13) = 13이며, 9 뒤에서 끝내면 max(17, 4) = 17입니다. 따라서 best[2][4] = 13입니다. 그러면 best[3][6]은 마지막 부분으로 [7, 3]을 시도해 max(13, 10) = 13을 얻으며, 다른 시작 위치로는 이보다 나은 결과를 얻을 수 없습니다.

문제는 계산량입니다. 행이 k개 있고, 행마다 끝 위치가 n개이며, 각 끝 위치마다 시작 위치를 최대 n개까지 시도하므로 단계 수는 최대 k·n²/2입니다. n = 5000이고 k = 2500이면 내부 반복문은 약 1.8 × 10^10번 실행됩니다. 초당 단순 연산을 10^9번 수행하더라도 18초가 걸립니다. 그래도 이 DP는 알아둘 가치가 있습니다. 값이 음수가 아니라고 가정하지 않으므로 빠른 방법이 통하지 않는 경우에도 계속 작동합니다.

알고리즘

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를 정하고 다음을 물어보세요. nums를 각 부분의 합이 c 이하가 되도록 k개의 부분으로 나눌 수 있을까요? 문제의 답은 이 질문에 예라고 답할 수 있는 가장 작은 상한입니다. 두 가지 이유로 이 질문은 원래 문제보다 훨씬 쉽습니다.

첫째, 한 번의 그리디 탐색으로 답을 구할 수 있습니다. 왼쪽에서 오른쪽으로 살펴보며 현재 부분의 합이 c 이하인 동안 값을 계속 더하세요. 다음 값을 더하면 합이 c를 초과하게 될 때 현재 부분을 끝내고, 그 값부터 새 부분을 시작하세요. 이 방법은 상한 이하로 나눌 수 있는 모든 분할 중 부분의 개수를 최소화합니다. 이를 다른 유효한 분할과 부분별로 비교해 보세요. 두 분할의 첫 부분은 모두 첫 번째 값에서 시작하고, 그리디는 다음 값이 들어가지 않을 때만 멈추므로 그리디의 첫 부분은 적어도 다른 분할만큼 오른쪽까지 이어집니다. 그러면 그리디의 두 번째 부분은 다른 분할의 두 번째 부분과 같거나 그보다 뒤에서 시작합니다. 그 부분의 끝까지 포함하는 그리디 부분의 값들은 다른 부분의 일부이며, 음수가 없으므로 일부의 합은 전체의 합보다 클 수 없습니다. 따라서 이 값들은 들어맞고, 그리디는 다시 적어도 그만큼 멀리까지 이어집니다. 그리디는 결코 뒤처지지 않으므로 필요한 부분의 개수가 더 많아지는 일은 없습니다.

둘째, 부분의 개수가 k보다 적어도 정확히 k인 것만큼 좋습니다. 그리디에 m < k개의 부분이 필요하다면, 값이 두 개 이상 들어 있는 부분을 둘로 나누세요. 값이 음수가 아니므로 나눈 두 부분의 합은 전체의 합보다 클 수 없습니다. 또한 n ≥ k이므로 k개에 도달할 때까지 이렇게 나눌 수 있는 부분이 항상 있습니다. 따라서 판정 조건은 partsNeeded(c) ≤ k입니다.

이제 핵심 성질을 살펴보겠습니다. 이 판정은 단조적입니다. 상한 c에서 가능하다면, 같은 분할이 더 큰 상한에도 들어맞으므로 c+1에서도 가능합니다. max(nums)부터 sum(nums)까지의 상한에 대한 답은 아니요, 아니요, ..., 아니요, 예, 예, ..., 예의 순서로 나타나며, 우리는 첫 번째 예를 찾으면 됩니다. 양 끝의 범위는 안전합니다. max(nums)보다 작은 상한으로는 그 값을 담을 수 없고, 전체 합은 항상 하나의 부분에 들어갑니다. 또한 첫 번째 예는 단순한 경계값이 아니라 실제 비용이기도 합니다. 해당 분할의 어떤 부분의 합도 정확히 c가 아니라면 상한 c-1로도 가능하기 때문입니다.

k = 3인 첫 번째 예시 [6, 2, 9, 4, 7, 3]을 추적해 보겠습니다. 상한은 9부터 31까지입니다. 상한 20에서는 [6, 2, 9], [4, 7, 3]으로 묶입니다. 부분이 2개이므로 가능하고, 범위는 9부터 20까지로 좁혀집니다. 상한 14에서는 [6, 2], [9, 4], [7, 3]으로 묶입니다. 부분이 3개이므로 가능하고, 범위는 9부터 14까지입니다. 상한 11에서는 [6, 2], [9], [4, 7], [3]으로 묶입니다. 부분이 4개이므로 불가능하고, 범위는 12부터 14까지입니다. 상한 13에서는 부분이 3개 필요하므로 가능하고, 범위는 12부터 13까지입니다. 상한 12에서는 4개가 필요하므로 불가능합니다. 따라서 답은 13입니다.

각 탐색은 n개의 값을 읽으며, 범위는 매번 절반으로 줄어듭니다. 합계 S가 최대 5 × 10^8이라면 값 5000개를 약 29회 탐색하므로 대략 150000단계가 필요합니다.

알고리즘

lo = max(nums)와 hi = sum(nums)를 설정합니다.
lo < hi인 동안 mid = lo + (hi - lo) / 2를 구합니다.
상한 mid에서 그리디 방식으로 필요한 부분의 개수를 셉니다. 부분을 1개로 시작하고 누적 합을 0으로 둡니다. 값을 더했을 때 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)보다 작게 시작하는 경우. 그리디 검사는 상한보다 큰 값을 별도의 부분에 넣고 계속 진행하므로, [1, 9]에 k = 2일 때 상한 5가 적절하다고 판단합니다. 가장 큰 값에서 시작하거나, 단일 값이 상한을 초과하면 검사에서 실패하도록 하세요.
partsNeeded(c) == k를 검사하는 경우. 그리디 방식은 종종 k보다 적은 부분을 필요로 합니다. [3, 0, 4]와 k = 3에서 상한 4는 [3, 0], [4]로 묶습니다. ==를 사용하면 어떤 상한도 통과하지 못합니다. 더 적은 부분은 항상 더 잘게 나눌 수 있으므로 ≤ k를 검사하세요.
부분 개수를 0부터 세는 경우. 첫 번째 부분은 값이 그 부분의 용량을 초과하기 전부터 존재하므로 개수는 1에서 시작합니다.
mid가 조건을 만족할 때 hi = mid - 1로 설정하는 경우. 이렇게 하면 답 자체를 건너뛸 수 있습니다. hi = mid로 유지하고 lo < hi인 동안 반복하세요.
DP의 i를 0에서 시작하는 경우. i < p-1인 best[i] 셀은 부분 개수보다 값의 개수가 적은 경우를 나타내는데, 어떤 분할로도 그렇게 만들 수 없으며 0으로 채워진 행에서는 비용이 0으로 읽힙니다. [100, 1, 1]에 k = 3을 사용하면 DP는 100 대신 2를 반환합니다. i를 p-1에서 시작하세요.
큰 한계값에서 발생하는 오버플로. 여기서는 합계가 최대 5 × 10^8이므로 32비트 정수로 저장할 수 있습니다. 값이 10^6에 이르면 2148개만으로도 이미 2^31-1을 넘으므로 64비트 합계를 사용하세요.

자주 묻는 질문4

Split Array Largest Sum의 시간 복잡도는 얼마인가요?

이분 탐색은 O(n log S) 시간에 실행됩니다. 여기서 n은 nums의 길이이고 S는 그 합입니다. 각 탐욕적 검사는 배열을 한 번 순회하며, 상한 범위는 검사할 때마다 절반으로 줄어듭니다. S = 5 × 10^8일 때 약 29번 검사합니다. 추가 공간은 O(1)을 사용합니다. DP는 O(k·n²) 시간과 O(n) 공간을 사용합니다.

실현 가능성 검사는 왜 단조적인가요?

어떤 분할의 각 부분의 합이 모두 최대 c라면, 같은 분할에서 각 부분의 합은 모두 최대 c+1입니다. 따라서 어떤 상한이 조건을 만족하면 그보다 큰 모든 상한도 조건을 만족하고, 어떤 상한이 조건을 만족하지 않으면 그보다 작은 모든 상한도 조건을 만족하지 않습니다. 답은 ‘아니요’가 이어진 다음 ‘예’가 이어지는 형태이므로, 경계를 찾는 데 필요한 것은 바로 이진 탐색입니다.

그리디 검사는 왜 부분의 개수가 가장 적은 경우를 찾을까요?

그리디 방식은 다음 값을 더하면 상한을 초과하게 될 때까지 한 부분에 값을 계속 더합니다. 이를 유효한 분할과 부분별로 비교해 보세요. 각 그리디 부분은 같은 번호의 다른 분할 부분이 시작하는 위치와 같거나 그 이후에 시작하므로, 해당 부분의 끝까지 포함하는 값들은 상한 이하인 부분의 일부입니다. 값은 음수가 아니므로 그 조각도 상한 이하이며, 그리디 방식은 적어도 그만큼 더 확장됩니다. 그리디 방식은 결코 뒤처지지 않으므로, 어떤 분할보다도 적은 부분으로 배열 전체를 포함합니다.

이진 검색은 음수에서도 작동하나요?

아니요. 음수 값이 있으면 값을 더했을 때 합이 작아질 수 있으므로, 그리디 방식은 너무 일찍 한 부분을 닫아 유효한 분할을 놓칠 수 있습니다. 한 부분을 나누면 한 조각의 합이 전체의 합보다 커질 수도 있으므로, 부분이 k개 미만이라고 해서 k개 부분으로 분할할 수 있다는 뜻은 더 이상 아닙니다. DP는 어느 가정도 하지 않으므로 O(k·n²) 시간에 올바르게 동작합니다.

Python

def splitArray(nums, k):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [6, 2, 9, 4, 7, 3]
k = 3

기대값