문제

문제 링크

해설

• 문제가 조금 난해하게 적혀있어서 이해하기 어렵습니다. 다시 정리하면 아래와 같습니다.

  주어지는 N개의 강의는 순서가 바뀌어선 안됩니다. N개의 강의를 M개의 블루레이에 넣으려고 합니다. 이때, 블루레이가 얼마나 팔릴지 알 수 없기 때문에 블루레이의 크기는 최소한으로 하려고 합니다. N개의 각 강의 길이가 분 단위로 주어질 때, 필요한 블루레이의 크기의 최솟값을 구하세요.

• N개의 강의를 어떤 기준시간(mid)으로 여러 블록으로 나눴을 때, 그 블록 개수의 합이 M이면 정답 후보라고 볼 수 있을 것입니다.
  • (예제 입력 1)을 봅시다. { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 강의가 있고 이를 3개의 블루레이에 담아야 합니다.
  • 기준시간이 17분이면, {1, 2, 3, 4, 5}(15) | { 6, 7}(13) | {8, 9}(17) 으로 3개의 블루레이에 각각 담을 수 있습니다.
  • 만일 기준시간이 16분이면 어떨까요? 마지막 블록인 {8, 9}가 17분이기 때문에 어쩔 수 없이 {8}, {9}로 나눠지므로, 블루레이가 4개 필요합니다.
• 기준시간 최댓값은 모든 강의 시간의 합이고, 최솟값은 강의시간 중 최댓값보단 커야합니다.
  • 블루레이에 강의를 넣기 위해서는 당연히 블루레이의 시간이 강의시간보다 커야겠지요?
  • 그리고, 블루레이의 시간 최댓값 시작점은 모든 강의시간의 합부터 시작하면 적당하겠지요?

코드

#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;
}

소스코드 링크

결과