문제 소개
숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 이 리스트를 비어 있지 않은 k개의 부분 리스트(sublist)로 나누려고 할 때, 각 부분 리스트의 원소 합 중 최댓값이 최소가 되도록 분할해야 합니다.
예를 들어 입력이 nums = [2, 4, 3, 5, 12], k = 2라면, 리스트를 [2, 4, 3, 5]와 [12]로 나눌 수 있습니다. 두 구간의 합은 각각 14와 12이므로, 이때 최댓값인 14가 정답이 됩니다.
풀이 전략: 이분 탐색과 탐욕적 검증
이 문제는 이분 탐색(Binary Search)과 탐욕적(Greedy) 검증 함수를 결합하면 효율적으로 해결할 수 있습니다. 핵심 질문은 다음과 같습니다.
“모든 부분 리스트의 합이 x 이하가 되도록 k개 이하의 그룹으로 나누는 것이 가능한가?”
이 질문에 빠르게 답할 수 있다면, 답이 될 수 있는 값의 범위에서 이분 탐색을 수행하여 최솟값을 찾아낼 수 있습니다.
알고리즘 단계
- 검증 함수 ok() 정의: 배열 v, 그룹 제한 k, 한계값 x를 인자로 받습니다.
- cnt := 0, sum := 0으로 초기화합니다.
- v의 각 원소 i에 대해 다음을 수행합니다.
- sum + i > x이면 새 그룹을 시작합니다(sum := i로 설정하고 cnt를 1 증가).
- 그렇지 않으면 현재 그룹에 계속 더합니다(sum := sum + i). - cnt <= k이면 true를, 아니면 false를 반환합니다.
- 메인 로직 초기화: low := 0, ret := 0, high := 0으로 설정합니다.
- nums의 각 원소 i에 대해 high와 ret에 i를 누적하고, low는 max(low, i)로 갱신합니다. 즉, 탐색 범위는 [원소의 최댓값, 전체 합]입니다.
- low <= high인 동안 다음을 반복합니다.
- mid := low + (high - low) / 2를 계산합니다.
- ok(nums, k - 1, mid)가 참이면 ret := mid로 갱신하고 high := mid - 1로 줄입니다.
- 거짓이면 low := mid + 1로 올립니다. - 반복이 종료되면 ret을 반환합니다.
ok() 호출 시 k - 1을 넘기는 이유는, cnt가 첫 번째 그룹을 제외한 ‘새로 시작된 그룹’의 개수를 세기 때문입니다. 실제 필요한 그룹 수는 cnt + 1이며, 이것이 k 이하이려면 cnt <= k - 1이어야 합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
bool ok(vector <int>& v, int k, int x){
int cnt = 0;
int sum = 0;
for(int i : v){
if(sum + i > x){
sum = i;
cnt++;
}
else{
sum += i;
}
}
return cnt <= k;
}
int solve(vector<int>& nums, int k) {
int low = 0;
int ret = 0;
int high = 0;
for(int i : nums){
high += i;
ret += i;
low = max(low, i);
}
while(low <= high){
int mid = low + ( high - low) / 2;
if(ok(nums, k - 1, mid)){
ret = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 3, 5, 12};
int k = 2;
cout << solve(v, k);
}
입력 및 출력
입력:
{2, 4, 3, 5, 12}, 2
출력:
14
시간 복잡도
검증 함수 ok()는 배열을 한 번 순회하므로 O(n)이며, 이분 탐색은 전체 합 S에 대해 O(log S)번 수행됩니다. 따라서 전체 시간 복잡도는 O(n log S)로, 완전 탐색보다 훨씬 효율적입니다.