백준 1202 보석도둑 c++ 풀이 (priority queue, vector, 우선순위 큐)

이 문제는 priority queue를 활용한 문제이다. 

우선 보석의 (무게, 값) 과 가방의 (무게) 가 주어진다.

여러개가 주어지는데 이때 가장 큰 가치를 가질 수 있도록 가방에 보석을 하나씩 담는다.(단 가방에 하나의 보석만 담을 수 있다.)

 

가장 작은 가방에 들어갈 수 있는 보석 중 가치가 큰 것을 담는다. 다음으로 큰 가방에 담을 수 잇는 보석 중 가치가 가장 큰 것을 담는다. 이후 가방이 없을 때까지 반복한다.

그렇다면 결국 가방은 순서대로 사용하면 되고, 보석도 가방에 들어갈 무게만큼 순서대로 대조하여 가방에 담으면 된다. 그래서 보석과 가방을 무게 순으로 정렬한다. 

이후에 pq에 보석을 넣어서 가장 가치가 높은것을 꺼내어 가방에 담는다.

 

1. 보석과 가방을 무게순으로 정렬

2. 가장 작은 가방을 꺼냄

3. 가방에 들어가는 보석을 전부 우선순위큐에 넣는다.(큐는 가치가 높은 보석이 루트 노드가 되어야 한다.)

4. 우선 순위 큐에서 가방에 보석을 하나 담는다.

5. 이후 루프를 돌며 가방이 남은 가방이 없을때 까지 반복한다.

6. 총량을 출력한다.

 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
int main() {
	priority_queue<pair<int,int>> pq;

	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> nv;
	vector <long> kv;
	int a, b;

	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		nv.push_back(pair<int, int>(a, b));
	}
	sort(nv.begin(), nv.end());
	
	for (int i = 0; i < k; i++) {
		cin >> a;
		kv.push_back(a);
	}
	sort(kv.begin(), kv.end());

	int bag;
	int ni = 0;
	long long sum = 0;
	for (int i = 0; i < k; i++) {
		bag = kv[i];
		while (ni < n && bag >= nv[ni].first) {// 값이 더 작으면 가능
			pq.push(pair<int, int>(nv[ni].second , nv[ni].first));
			ni++;
		}
		if (!pq.empty()) {
			pair<int, int> tmp = pq.top();
			pq.pop();
			sum += tmp.first;
		}
	}
	cout << sum << '\n';
}

우선순위큐를 이런식으로 사용할 수 있다는 것을 알게 되었다.

솔직히 혼자풀게 된다면 쉽게 풀지 못할거 같다. 효율적으로 연산하기 위해 미리 정렬을 시켜준다거나 우선순위에 넣고 빠르게 최댓값만을 꺼내는 로직은 떠올리기 어려운거 같다. 

 

결론 : c++에서 우선순위 큐는 priority_queue로 사용가능하며 pair<2개> 를 사용 가능하다. 개꿀이다. stl만 잘 익숙해지면 좀 더 편하게 코딩이 가능할 것 같다.