[C++] 백준 22254번: 공정 컨설턴트 호석

문제 링크

22254번: 공정 컨설턴트 호석

문제 요약

N개의 선물을 생산해야 한다. 각 선물은 여러 개의 생산라인에서 병렬 생산이 가능하다. 각 선물의 차례가 오면, 생산이 가장 빨리 끝나는 생산라인에 할당된다. 이때 모든 선물을 X시간 이내에 생산하기 위한 최소 생산라인의 수를 구해야 한다.

접근 방법

1 ~ 100000 사이를 매개변수 탐색하면서 생산라인의 수를 구합니다. 생산라인의 수가 적합한지 부적합한지는 우선순위 큐를 이용하면 됩니다.

먼저 우선순위 큐에 생산라인의 수만큼 0을 삽입해줍니다. 그리고, 우선순위큐에서 하나씩 빼서 현재 선물의 생산시간을 더해서 다시 넣어줍니다. 만약 하나의 원소라도 X를 초과하면 false를 반환합니다. 모든 선물을 삽입해주었음에도 X를 초과하는 원소가 없다면 true를 반환합니다.

이분탐색 구현에서 실수를 많이 할 수가 있는데, true가 반환된 경우에는 high를 갱신하고, false가 반환된 경우에는 low를 갱신해주면 됩니다. 이 글을 참고하면 이분탐색도 실수하지 않을 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, x;
vector<int> v;

bool func(int k) {
	priority_queue<int, vector<int>, greater<int>> pq;
	
	for (int i = 0; i < k; i++) pq.push(0);

	for (auto& i : v) {
		int tmp = pq.top();
		pq.pop();

		tmp += i;

		if (tmp > x)
			return false;

		pq.push(tmp);
	}

	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> x;
	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];

	int low = 1, high = 100001, ans = 0;
	while (low <= high) {
		int mid = (low + high) / 2;

		if (func(mid)) {
			high = mid - 1;
			ans = mid;
		}
		else
			low = mid + 1;
	}

	cout << ans << '\n';
	return 0;
}