주어지는 N개의 강의는 순서가 바뀌어선 안됩니다. N개의 강의를 M개의 블루레이에 넣으려고 합니다. 이때, 블루레이가 얼마나 팔릴지 알 수 없기 때문에 블루레이의 크기는 최소한으로 하려고 합니다. N개의 각 강의 길이가 분 단위로 주어질 때, 필요한 블루레이의 크기의 최솟값을 구하세요.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 100'001;
int N, M, arr[MAX_N];
int low, high, mid, maxTime, ans;
bool isAvailable(int limit) {
if (maxTime > limit) return false;
int cnt = 0, sum = 0;
for (int i = 0; i < N; ++i) {
sum += arr[i];
if (sum > limit) sum = arr[i], cnt++;
}
// 마지막 강의 그룹은 cnt++에 안 들어가므로 +1 해줘야 합니다.
return cnt + 1 <= M;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
cin >> arr[i];
high += arr[i];
maxTime = max(maxTime, arr[i]);
}
while (low <= high) {
mid = low + (high - low) / 2;
if (isAvailable(mid)) high = mid - 1, ans = mid;
else low = mid + 1;
}
cout << ans;
}