여러 개의 청크(chunk)로 구성된 초콜릿 바가 하나 있고, 각 청크에는 고유한 단맛(sweetness)이 리스트 형태로 주어져 있다고 가정해 봅시다. 이 초콜릿을 K명의 친구들과 나누려면 K번 잘라서 총 K+1개의 조각을 만들어야 하며, 각 조각은 연속된 여러 개의 청크로 이루어집니다. 그중 단맛의 합이 가장 작은 조각을 자신이 가져가고 나머지는 친구들에게 준다고 할 때, 초콜릿을 최적으로 잘라서 얻을 수 있는 조각의 최대 단맛 합을 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 sweetness = [1,2,3,4,5,6,7,8,9], K = 5라면 출력은 6이 됩니다. 초콜릿을 [1,2,3], [4,5], [6], [7], [8], [9]와 같이 나누면 되기 때문입니다.
접근 방법: 이진 탐색
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. "단맛의 합이 특정 값 x 이상인 조각을 K+1개 만들 수 있는가?"라는 질문은 x가 커질수록 만들 수 있는 조각 수가 줄어드는 단조적(monotonic) 성질을 가지므로, 가능한 범위 내에서 이진 탐색을 수행하면 답을 찾을 수 있습니다.
해결 과정은 다음과 같습니다.
ok() 함수를 정의합니다. 이 함수는 배열 v, 필요한 조각 수 cuts, 기준값 maxVal을 매개변수로 받습니다.
counter := 0, temp := 0으로 초기화합니다.
i := 0부터 배열 v의 크기까지 반복하며 다음을 수행합니다.
temp가 maxVal보다 크거나 같으면 counter를 1 증가시키고 temp를 0으로 초기화합니다.
i가 배열 v의 크기와 같으면 반복문을 종료합니다.
temp에 v[i]를 더합니다.
counter가 cuts보다 크거나 같으면 true를 반환합니다.
메인 메서드에서는 다음을 수행합니다.
maxa := -1로 초기화합니다.
n := 배열 s의 크기
low := 0, high := 0으로 초기화합니다.
i := 0부터 n 미만까지 반복하면서 low는 s[i] 중 최솟값으로, high에는 s[i]의 누적 합을 저장합니다.
high를 1 증가시킵니다.
low가 high보다 작은 동안 다음을 반복합니다.
mid := low + (high - low + 1) / 2
ok(s, k + 1, mid)가 참이면 low := mid로 갱신합니다.
그렇지 않으면 high := mid - 1로 갱신합니다.
low를 반환합니다.
알고리즘 동작 원리
ok() 함수는 탐욕적(greedy) 방식으로 배열을 순회하면서 합이 maxVal 이상이 되는 조각이 몇 개나 만들어지는지 계산합니다. 이진 탐색은 "K+1개 이상의 조각을 만들 수 있는" 가장 큰 maxVal 값을 찾아내며, 그 값이 곧 우리가 가져갈 수 있는 조각의 최대 단맛 합이 됩니다. 전체 시간 복잡도는 O(n log S)로, 여기서 n은 청크의 개수, S는 단맛의 총합입니다.
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector <int> v, int cuts, int maxVal){
int counter = 0;
int temp = 0;
for (int i = 0; i <= v.size(); i++) {
if (temp >= maxVal) {
counter++;
temp = 0;
}
if (i == v.size()) {
break;
}
temp += v[i];
}
return counter >= cuts;
}
int maximizeSweetness(vector<int>& s, int k) {
int maxa = -1;
int n = s.size();
int low = 0;
int high = 0;
for (int i = 0; i < n; i++) {
low = min(low, s[i]);
high += s[i];
}
high++;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (ok(s, k + 1, mid))
low = mid;
else
high = mid - 1;
}
return low;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9};
cout << (ob.maximizeSweetness(v, 5));
}
입력
{1,2,3,4,5,6,7,8,9}, 5
출력
6