[백준][1202][C++] 보석 도둑

링크

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

1202번: 보석 도둑

해설

가방에 하나씩밖에 못 넣고 여러 개의 가방이 있으므로 각 가방에 넣을 수 있는 최대의 value 를 넣으면

최적화가 되므로 그리디 하게 넣으면 됩니다.

 

1. 보석과 가방을 모두 오름차순으로 정렬해두고 priority_queue(max heap) 를 준비합니다.

2. 가방에 대해 loop 를 만들고 각 가방 차례마다 넣을 수 있는 가장 큰 보석까지 priority_queue 에 넣습니다.

3. 이때 priority_queue 에는 보석의 가치만 넣으면 되므로 가치값만 넣습니다.

4. 그러면 priority_queue 의 top에는 현재 가방에 넣을 수 있는 가장 높은 가치가 있게 됩니다.

    물론 가방에 넣을 수 있는 보석이 하나도 없을 수도 있으니 체크합니다.

5. 정답에 += 하고 pop 하는 작업을 가방 끝까지 합니다. 

 

아래 코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int N, K, BAG[300000];
long long ANS = 0;
pair <int, int> GEM[300000];
priority_queue <int> que;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> K;
 
	for (int i = 0; i < N; ++i)
		cin >> GEM[i].first >> GEM[i].second;
	
	for (int i = 0; i < K; ++i)
		cin >> BAG[i];
 
	sort(GEM, GEM + N);
	sort(BAG, BAG + K);
 
	int idx = 0;
 
	for (int i = 0; i < K; ++i) {
		while (idx < N && GEM[idx].first <= BAG[i]) {
			que.push(GEM[idx].second);
			++idx;
		}
		if (!que.empty()) {
			ANS += que.top();
			que.pop();
		}
	}
 
	cout << ANS;
 
	return 0;
}