보석 도둑 (백준)

그리디 알고리즘을 사용하는 문제였다. 

 

처음 접근 방법은 가방의 무게는 오름차순으로, 보석은 가격의 내림차순으로 정렬한 후 가격이 비싼 보석부터 가방에 넣도록하였다. 넣은 보석은 컨테이너에서 제거하였다. 이렇게 해서 올바른 정답이 나왔다.

 

하지만 컨테이너에서 erase(iterator)로 제거하는 방식은 O(n)이다. 여기에 보석들을 순회 돌기 위한 첫번째 반복문, 넣을 수 있는 가방을 찾기위한 두번째 반복문이 있기 때문에 총 O(n^3)의 시간 복잡도가 된다. 결국 시간 초과로 오답이 났다.

 

그래서 연산 시간을 좀 더 줄이고자 erase(iterator)를 제거하기 위해 Heap을 사용하였다. Heap에 가방에 담을 수 있는 만큼의 무게의 보석들을 담아놓는다. 이때 Heap은 가격 기준의 최대 힙으로 설정되어 있으므로 현재 가방 무게에 맞는 가장 비싼 보석이 컨테이너에서 먼저 오게된다. 이 보석을 가방에 담아주면 최대 가격으로 담을 수 있다.

 

코드는 다음과 같다.

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

int main()
{
	int jewelry_count, bag_count;
	cin >> jewelry_count >> bag_count;
	vector<pair<int, int>> jewelry(jewelry_count);
	for (int i = 0; i < jewelry.size(); ++i)
		cin >> jewelry[i].first >> jewelry[i].second;
	vector<int> bag(bag_count);
	for (int i = 0; i < bag.size(); ++i)
		cin >> bag[i];

	long long result = 0;
	priority_queue<int, vector<int>> pq; // 가장 비싼 보석을 담기 위한 Heap
	sort(jewelry.begin(), jewelry.end());
	sort(bag.begin(), bag.end());
	int j = 0;
	for (int i = 0; i < bag.size(); ++i)
	{
        // 현재 가방에 담을 수 있는 모든 보석을 Heap에 넣는다.
		while (j < jewelry.size() && jewelry[j].first <= bag[i])
			pq.push(jewelry[j++].second);

        // 담을 수 있는 보석중 가장 비싼 보석을 가방에 넣는다.
		if (!pq.empty())
		{
			result += pq.top();
			pq.pop();
		}
	}
	cout << result << endl;
}