[백준/BOJ] 백준 1202번 : 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

보석을 무게 오름차순으로 정렬하고, 가방도 최대 무게 오름차순으로 정렬한 뒤 최대 무게가 작은 가방부터 넣을 수 있는 보석 중 가장 큰 가치를 넣는 방법을 통해 문제를 해결했다. 가방을 정렬했으므로 현재 가방에 넣을 수 있는 보석이면 다음 가방에서도 넣을 수 있다는 것을 이용해서 현재 가방에 넣을 수 있는 보석의 가치를 모두 우선순위 큐에 넣고 우선순위 큐에 들어있는 보석은 중복해서 넣지 않도록 주의하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n, k;
deque<pair<int, int>> gold; //(무게, 가격)
vector<int> bag;
priority_queue<int> able_gold; //가방에 넣을 수 있는 보석의 가치 저장

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int m, v;
		cin >> m >> v;

		gold.push_back(make_pair(m, v));
	}

	for (int i = 0; i < k; i++)
	{
		int c;
		cin >> c;

		bag.push_back(c);
	}

	sort(gold.begin(), gold.end()); //보석을 무게 오름차순으로 정렬
	sort(bag.begin(), bag.end()); //가방을 최대 무게 오름차순으로 정렬

	long long result = 0;

	//최대 무게가 작은 가방 부터 넣을 수 있는 보석중 가장 큰 가치를 넣는다
	for (int i = 0; i < bag.size(); i++)
	{
		//현재 가방에 넣을 수 있는 보석의 가치를 모두 우선순위 큐에 저장한다
		while (gold.size() != 0 && gold[0].first <= bag[i])
		{
			able_gold.push(gold[0].second);
			gold.pop_front();
		}

		if (able_gold.size() != 0)
		{
			result += (long long)able_gold.top();
			able_gold.pop();
		}
	}

	cout << result;

	return 0;
}