백준 22254. 공장 컨설턴트 호석 - 문제풀이 (c++) (이분 탐색)

🔎 22254. 문제 보기

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

---

💡 문제 풀기 전

처음에 봤을때 n^2은 10^10이라 1초를 초과하는 것을 알았다. 그래서 nlog(n) 방법을 찾아야 했다.

---

📝 코드 보기

#include <bits/stdc++.h>
using namespace std;

int n, x;
int arr[100000];


bool f(int mid) {
	priority_queue<int, vector<int>, greater<int>> pq;
	
	for(int i=0; i<mid; i++) {
		pq.push(0);
	}
	
	for(int i=0; i<n; i++) {
		int top=pq.top();
		pq.pop();
		
		if(top+arr[i]>x) {
			return false;
		}
		pq.push(top+arr[i]);
	}
	
	return true;
}

int main() {
	cin >> n >> x;
	for(int i=0; i<n; i++) {
		cin >> arr[i];
	}
	
	int l=1, r=n, answer=0;	
	while(l<=r) {
		int m = (l+r)/2;
		if(!f(m)) {
			l=m+1;
		} else {
			r=m-1;
		}
	}
	
	cout << r+1;
	return 0;
}

---

🎈 코드 풀이 및 관련 개념

• 우선순위 큐: priority_queue<int, vector, greater> pq;
• 이분 탐색

풀이.

1. 우선 이분 탐색의 기준은 공정의 개수이다. 즉 공정의 개수는 최소 1개, 최대 n개이다
   (l=1, r=n)

2. 공정의 개수를 이분 탐색 하면서 우선순위큐에 공정의 개수 만큼 0(가장 작은 값)을 넣는다. -> 처음 기본 값을 만들기 위해서다.

   예를 들어
   6 11
   5 2 8 4 3 5 공정이 3개일 때의 초기 값은
   공정 1: 5
   공정 2: 2
   공정 3: 8

3. 공정에 초기값을 만든 후 오름차순으로 된 우선순위큐에서 가장 작은값에 i번 선물 제작시간을 더한다.

---

과정. (예제 입력의 경우)

공정 1: 5 (5)
공정 2: 2 (2)
공정 3: 8 (8)
공정 2: 2 4 (6)
공정 1: 5 3 (8)
공정 2: 2 4 5 (11)

---

결과. (예제 입력의 경우)

공정 1: 5 3 (8)
공정 2: 2 4 5 (11)
공정 3: 8 (8)