어떤 시뮬레이터로서의 우선순위 큐

우선순위 큐의 개념은 "우선순위"를 기반으로 큐에서 POP 하는 것을 의미한다

그냥 큐는 "들어온 순서" 를 우선순위로 갖는 우선순위 큐라고 이해하는 편이 좋다.

 

암튼, 이 우선순위는 일종의 정렬된 상태를 유지한다고 이해해도 좋다

e.g) 3개의 아이템들이 유지되는데, 여기서 제일 적은 놈을 뽑아서 값을 추가하며 나아감

 

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

 

이 문제가 정확히 이에 해당한다. N개의 공정을 가정하고, 그 공정이 우선순위 큐 안에 있는 아이템으로 취급한다.

그리고 N개의 공정이 조건을 만족하냐? 만족 안하냐? 를 찾는 일종의 파라메트릭 서치라고 이해하면 될듯 하다.

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, M;
vector<int> items(100005);
bool isValidTarget(int target) {
	priority_queue<int, vector<int>, greater<int>> pq;
	bool validTarget = true;
	// 공정 TARGET 개 만큼 push
	for (int i = 0; i < target; i++) {
		pq.push(0);
	}
	for (int i = 0; i < N; i++) {
		// n만큼 순회하면서 때려줍시다
		int current = pq.top();
		pq.pop();
		int next = current + items[i];
		if (next > M) {
			// 먼 짓을 해도 이 target 으로는 안됩니다
			validTarget = false;
			break;
		}
		// 어 아무튼 난 queue 에 넣을테니깐 계속 돌아봐
		pq.push(next);
	}
	return validTarget;

}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> items[i];
	}

	// 2개의 공정에서 최대 값?
	// 전체 넣고 2개씩 pop 해서 최대를 구하면 됨

	int start = 1;
	int end = N;
	int ans = N;

	while (start <= end) {
		int target = (start + end) / 2;
		bool validTarget = isValidTarget(target);
		if (validTarget) {
			// 처리 됨 & target 을 줄여봐
			ans = (ans < target) ? ans : target;
			end = target - 1;
		}
		else {
			// 처리가 안된다는데? start를 늘려봐
			start = target+1;
		}
	}
	cout << ans << endl;
    return 0;
}

 

우선순위 큐 문제는 변형이 많이 되는 것 같은데. 그냥 그룹에서 어떤 조건으로 뽑는다! 라는 개념과 함께 가면 좋을듯