백준 1202 보석 도둑

 

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

1202번: 보석 도둑

---

접근법

1. 가장 작은 용량의 가방에 들어 갈 수 있는 보석을 찾기 위해 오름차순 정리를 한다. (보석과 가방 모두)2. 그 중 가장 비싼 보석을 찾기 위해 우선순위 큐를 사용한다.3. 가장 작은 용량의 가방에 들어간 보석은 더 큰 가방에도 들어 갈 수 있으므로 그리디 탐색을 사용한다.

---

풀이

1. 가방과 보석을 오름차순으로 정리한다.2. 가방을 순회한다.3. 가방에 담을 수 있는 보석을 순회하고, 가방보다 무게가 작거나 같다면 큐에 담는다.4. 큐의 top()으로 가장 비싼 보석을 가져온다.

#include "pch.h"

#define MAX 300001

pair<int, int> jewerly[MAX];
int bag[MAX];
int N, K;
int answer = 0;

int main()
{
	cin >> N >> K;

	int M, V;

	for (int i = 0; i < N; ++i)
	{
		cin >> M >> V;

		jewerly[i] = {M, V};
	}

	int C;

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

	sort(jewerly, jewerly + N);
	sort(bag, bag + K);

	priority_queue<int> que;
	int idx = 0;

	for (int i = 0; i < K; ++i)
	{
		priority_queue<int> que;

		while (idx < N && bag[i] >= jewerly[idx].first)
		{
			que.push(jewerly[idx].second);
			++idx;
		}


		answer += que.top();
	}
	cout << answer << endl;
	return 0;
}

다르게 풀어봤는데 왜 틀렸는지 모르겠다.