[C++] 백준 2343번 - 기타 레슨

 

문제 2343번

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

mid의 조건을 블루레이 크기로 잡는다. 여기서 최소 블루레이의 크기는 담을 수 없는 경우는 배제해야되기 때문에 배열에서 가장 큰 요소로 넣어준다. 그리고 가장 큰 블루레이는 모든 요소의 합(100000(최대N)*10000(최대강의길이))이 된다. 강의들을 sum에 합치다가 sum이 임의로 잡아준 블루레이 크기(mid)보다 크면 블루레이 개수를 하나 증가시키고 sum을 다시 0으로 만들어 준 뒤 i가 하다가 if문에 걸려서 안 포함되었으니 i를 하나 빼 포함되도록 해준다. 그렇게 count해서 블루레이 개수가 M보다 크거나 같으면 블루레이 크기를 늘려주고 아니면 블루레이 크기를 줄여준다.블루레이 크기의 최소를 구하는 것이기 때문에 start를 출력해준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int Max = 0;
int N, M;
int* lecture;

int binarySearch() {
	int start = Max;
	int end = 1000000000;
	while (start <= end) {
		int mid = (start + end) / 2;
		int sum = 0, count = 0;
		for (int i = 0; i < N; i++) {
			sum += lecture[i];
			if (sum > mid) {
				count++;
				sum = 0;
				i--;
			}
		}
		if (count >= M) {	//블루레이 개수가 많으면
			start = mid + 1;	//블루레이 크기를 늘려줌
		}
		else {
			end = mid - 1;
		}
	}
	return start;
}

int main() {
	cin >> N >> M;
	lecture = new int[N];
	int* blue = new int[M];
	for (int i = 0; i < N; i++) {
		cin >> lecture[i];
		Max = max(lecture[i], Max);
	}
	cout << binarySearch();

	return 0;
}