이진 탐색 응용 문제 - 1

이진 탐색과 관련한 문제를 소개하려 한다.

아래 문제가 이진 탐색인 이유는 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 하기 때문이다. 블루레이의 크기(mid 값)을 늘리거나 줄여가면서 풀 수 있는 문제이다.

 

백준 - 2343: 블루레이 만들기

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

2343번: 기타 레슨

 

코드

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int lesson, blue, n;
	int s = 0, e = 0;

	cin >> lesson >> blue;
	vector <int> num(lesson);

	for (int i = 0; i < lesson; i++) {
		cin >> n;
		num[i] = n;

		if (s < num[i]) { // 이진 탐색의 시작 인덱스: 최대 레슨 시간
			s = num[i];
		}
		e += num[i]; // 이진 탐색의 마지막 인덱스: 모든 레슨 시간의 합
	}

	// sort(num.begin(), num.end());

	
	while (s <= e) {

		int mid = (s + e) / 2;
		int sum = 0;
		int cnt = 0;

		// mid 값으로 모든 레슨을 저장할 수 있는지 확인해보기

		// 현재 mid값에 해당하는 블루 레이 개수 세기
		for (int i = 0; i < lesson; i++) {
			if (sum + num[i] > mid) {
				cnt++;
				sum = 0;
			}

			sum += num[i];
		}
			
		if (sum != 0) { 
			cnt++;
		}

		if (cnt > blue) { // mid 값 크기로 블루 레이에 모든 레슨을 저장할 수 없으면 시작 인덱스는 mid + 1 
			s = mid + 1;
		}
		else { // mid 값 크기로 블루 레이에 모든 레슨을 저장할 수 있으면 종료 인덱스는 mid - 1 
			e = mid - 1;
		}
	}
	cout << s << endl;
}