[C++] 백준 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;
}
Author And Source
이 문제에 관하여([C++] 백준 22254번: 공정 컨설턴트 호석), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beclever/C-백준-22254번-공정-컨설턴트-호석저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)