[G3] 백준 22254번 공정 컨설턴트 호석 C++ 이분탐색, 우선순위 큐, 매개변수 탐색

리뷰

 

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

처음 접하는 유형의 파라매트릭 서치 문제, 한 5분정도 생각해보니 아이디어가 떠올랐다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 맞춤형 선물의 제작 시간을 저장할 배열
• n : 맞춤형 선물의 개수를 저장할 변수
• x : 제작 완료까지 남은 시간을 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, x값을 입력 받고, n개의 맞춤형 선물의 제작 시간을 입력 받아 arr배열을 초기화한다.
2. 변수 l을 1, r을 n, ans를 n으로 초기화한다.
3. l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.
4. 변수 mid를 (l+r)/2로 초기화한다.
5. 최소힙 pq를 초기화하고, pq에 mid개만큼 0을 push해준다.
6. 변수 flag를 true로 초기화한다.
7. arr을 순회하며 변수 t에 arr[i]를 저장한다.
8. 변수 c에 pq.top()을 저장하고, pq.pop()처리를 해준다.
9. 만약 c+t가 x보다 크다면 flag를 false로 변경하고 break처리해준다.
10. 위 조건에 해당하지 않으면 pq에 c+t를 push해준다.
11. 만약 flag가 true일 경우 ans에 mid를 저장하고, r을 mid-1로 저장한다.
12. flag가 false일 경우 l을 mid+1로 저장한다.
13. ans에 최종적으로 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 처음엔 mid개만큼 최소힙을 생성하고, 선형 탐색을 해야하나 고민하였다.
2. 하지만 이럴 경우 최대 n*n크기만큼 순회해야 하므로 10억번 연산으로 인해 시간 초과가 발생한다는 것을 깨달았다.
3. 각 선물의 공정 시간은 X이하이며, 모든 시간은 자연수라는 조건이 있으므로 pq에 mid개만큼 0을 추가해주었다.

 

정답 코드

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

const int N = 1e5;
int arr[N];
int n, x;

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

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

	int l = 1, r = n, ans = n;
	while (l <= r) {
		int mid = (l + r) / 2;
		priority_queue<int, vector<int>, greater<int>> pq;
		for (int i = 0; i < mid; ++i) pq.push(0);

		bool flag = true;
		for (int i = 0; i < n; ++i) {
			int t = arr[i];
			int c = pq.top(); pq.pop();

			if (c + t > x) {
				flag = false;
				break;
			}
			
			pq.push(c + t);
		}

		if (flag) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans;
}