백준 1202 보석 도둑

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

1202번: 보석 도둑

 

우선순위 큐를 이용하는 문제인데... 이런게 정말 창의력 문제라고 생각한다.

 

어떻게 이런 풀이를 생각하는건지... 결국 풀지 못하고 다른 사람의 답을 봤다.

 

그리고 30분동안 감탄했다. 이 문제를 내는 사람이나, 푸는 사람이나... 대단해

 

이 문제에서 중요한 점은 가방에 들어갈 수 있는 보석의 무게가 '최대'라는 점이다.

 

즉 10kg을 넣을 수 있는 가방이라도 3kg만 넣어도 된다. 이게 이 문제에서 중요한 점이다.

 

대소 관계를 따져보자면

 

1kg 가방에 들어가는 보석은 10kg 가방에도 들어가지만

10kg 가방에 들어가는 보석이라고해서 1kg에 들어가는 건 아니다.

 

그러므로 더 가벼운 가방(?) 부터 차례대로 보석을 챙긴다.

 

/* 보석 도둑 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, K;
vector<pair<int, int>> jewelry;
vector<int> backpack;

void input();
void solve();

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

	input();
	solve();

	return 0;
}

void input() {
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		jewelry.push_back({ a,b });
	}

	for (int i = 0; i < K; i++) {
		int a; cin >> a;
		backpack.push_back(a);
	}
}

void solve() {
	sort(jewelry.begin(), jewelry.end());
	sort(backpack.begin(), backpack.end());

	priority_queue<int> pq;
	long long int result = 0;
	for (int i = 0, j = 0; i < K; i++) {
		while (j < N && jewelry[j].first <= backpack[i]) {
			pq.push(jewelry[j++].second);
		}

		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}

	cout << result << '\n';
}