[백준 1202] 보석 도둑

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

1202번: 보석 도둑

요구사항

최대한 많은 보석을 훔쳐오기

 

풀이

최대한 많은 보석을 훔치기 위해서는

제일 작은 용량을 가진 가방에 들어갈 수 있는 제일 비싼 보석을 넣어야 한다.

이것을 풀기 위하여

1. 현재 가방에 넣을 수 있는 무게의 모든 보석을 우선 순위 큐에 넣는다

2. 우선순위 큐 제일 위에 있는것이 현재 가방에 넣을 수 있는 가장 비싼 보석의 값이다

 

https://js1jj2sk3.tistory.com/14

를 참조하였다.

 

초기 풀이는 

비슷한 풀이 방식이였으나

1 우선 순위 큐에 넣은 다음 top을 제외하고는 다시 우선 순위 큐에 넣는 방식으로 풀어서 fail

 

 

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

using namespace std;
typedef long long ll;
struct go {
	ll weight;
	ll value;
};

ll n, k;
go map[300300];
ll bag[300300];
bool com(go a, go b) {
	if (a.weight < b.weight) return true;
	return false;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		go temp;
		scanf("%lld%lld", &temp.weight, &temp.value);
		map[i] = temp;
	}
	for (int i = 0; i < k; i++) {
		scanf("%lld", &bag[i]);
	}
	sort(bag, bag + k);
	sort(map, map + n, com);
	priority_queue<ll> q;
	ll ans = 0;
	for (int i = 0, j=0; i < k; i++) {
		ll now = bag[i];
		while (j < n && now >= map[j].weight) {
			q.push(map[j].value);
			j++;
		}

		if (!q.empty()) {
			//cout << "!" << endl;
			//cout << q.top() << endl;
			ans +=q.top();
			q.pop();
		}
	}
	cout << ans << endl;
}