백준 2343번 (Silver 1)

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

간단한 이진 탐색 문제이다.

 

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

template<typename T>
int BinarySearch(const T&, int);
int main() {
	cin.tie(0)->sync_with_stdio(false);
	int lessonNum, bluRayNum;
	cin >> lessonNum >> bluRayNum;
	vector<int> v(lessonNum);
	
	for (auto& it : v) {
		cin >> it;
	}
	cout << BinarySearch(v, bluRayNum);

	return 0;
}

template<typename T>
int BinarySearch(const T& container, int bluRayNum) {
	typename T::const_iterator iter = container.cbegin();
	int size = container.size();
	unsigned int max = 0;
	unsigned int min = 0;


	for (auto it = iter; it != container.cend(); ++it) {
		max += (*it);
		if (min < (*it))
			min = (*it);
	}

	while (max >= min) {
		int mid = (min + max) / 2;
		int bluRayCount = 1;
		unsigned int tmp = 0;

		for (auto it = iter; it != container.cend(); ++it) {
			if ((tmp + (*it)) > mid) {
				bluRayCount++;
				if (bluRayCount > bluRayNum) {
					break;
				}
				tmp = (*it);
			}
			else {
				tmp += (*it);
			}
		}

		if (bluRayCount > bluRayNum) { // 블루레이의 크기가 부족
			min = mid + 1;
		}
		else {
			max = mid - 1;
		}
	}
	

	return min;
}

블루레이의 크기를 이진 탐색으로 찾아내는 코드이다.

이진 탐색 후에 최솟값 min을 중간값 + 1을 넣거나 최댓값 max에 중간값 -1을 넣기 때문에, min이 max보다 커지면 루프를 빠져나오게 선언한다.

 

또한 max값은 블루레이 크기를 설정할 수 있는 가장 큰 값중 작은값으로 점점 낮아질 것이고, min값은 블루레이 크기를 설정할 수 없는 가장 큰 값으로 점점 커질 것이기 때문에 min이 max값보다 커지는 그 값이 블루레이 크기가 가장 작으면서 우리가 원하는 크기일 것이다.