[BOJ] 1202 보석 도둑

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

1202번: 보석 도둑

알고리즘: Greedy

 

 

접근:

1. 가방에는 보석을 한 개만 넣을 수 있다.

-> 각 가방은 본인이 담을 수 있는 보석 중에 가장 가치가 큰 보석을 가져야 한다. (Greedy 방식 접근)

 

다만, 무턱대고 가장 가치가 큰 보석을 집으면 안됨.

ex)

3 2

1 100

11 20

3 1

20

5

 

무게가 20인 가방이 무턱대고 가장 가치가 높은 1짜리 보석을 넣으면

그 밑에 무게가 5인 가방이 그 다음 가치가 높은 11짜리 보석을 넣을 수가 없다.

 

반면에, 무게가 20인 가방이 11짜리 보석을 넣은 후 무게가 5인 가방이 1짜리 보석을 넣으면 가치를 최대로 할 수 있다.

 

-> 보석이랑 가방 모두 무게의 오름차순으로 정렬 한 후,

    가져갈 수 있는 무게의 보석 중에서 가치가 최대인 것을 가져가면 된다.

 

//1202 보석도둑

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> ii;

int N, K, t;
long long int sum;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	vector<ii> jewel(N);	// first: M, second: V
	vector<int> C(K);
	priority_queue<int> pq;
	
	for (int i = 0; i < N; i++)
		cin >> jewel[i].first >> jewel[i].second;
	for (int i = 0; i < K; i++)
		cin >> C[i];
	
	sort(jewel.begin(), jewel.end());
	sort(C.begin(), C.end());
	
	int j = 0;
	for (int i = 0; i < K; i++)
	{
		while (j < N && jewel[j].first <= C[i])
		{
			pq.push(jewel[j].second);
			j++;
		}
		
		if(!pq.empty())
		{
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum;
	return 0;
}