[백준 C++] 1202 보석 도둑 - 그리디

1202번: 보석 도둑

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

typedef long long ll;
typedef pair<int, int> jewel;

jewel Jewel[300000];
int Bag[300000];
priority_queue<int> PQ;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; ++i)
	{
		cin >> Jewel[i].first >> Jewel[i].second;
	}

	for (int i = 0; i < K; ++i)
	{
		cin >> Bag[i];
	}

	sort(Jewel, Jewel + N);
	sort(Bag, Bag + K);

	ll Value = 0;
	int Ji = 0;
	for (int i = 0; i < K; ++i)
	{
		int M = Bag[i];
		while (Ji < N && Jewel[Ji].first <= M)
		{
			PQ.emplace(Jewel[Ji].second);
			++Ji;
		}

		if (PQ.empty())
		{
			continue;
		}

		Value += PQ.top();
		PQ.pop();
	}

	cout << Value;
}

---

 

우선순위 큐 자료구조를 이용해서 푸는 그리디 알고리즘 유형의 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 보석 배열(무게, 가격) 초기화, 무게 오름차순 정렬

2. 가방 배열 초기화, 무게 오름차순 정렬

3. 가방 배열 순차 탐색

3-a. 현재 가방에 들어가는 보석은 모두 우선순위 큐(가격 내림차순 정렬)에 저장

3-b. 우선순위 큐에 저장된 보석 중 가장 가격이 높은 보석 선택