[백준] 1202. 보석 도둑

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

1202번: 보석 도둑

냅색이긴 한데.. 느낌이 달랐다.

 

이 문제의 핵심은 가방 하나에 넣을 수 있는 보석들 중, 가장 가치가 높은 보석을 넣어야한다는 것이다.

 

먼저 떠올린 해법은 가방 하나에 보석 전체를 순회하면서 가장 가치가 높은 것을 넣는 것이었지만, 이는 O(N*K)이고 N과 K는 둘다 300,000이 최대이므로 TLE가 난다.

 

가방을 하나씩 잡고 검사해야하는 부분은 줄일 방도가 없으므로 보석 전체를 순회하는 부분에서 승부를 봐야했다.

 

다음으로 가방과 보석을 무게 기준으로 오름차순 정렬한 후, 비교하려는 생각을 했다.

매번 잡는 가방의 무게를 넘지않는 보석들을 전부 고르면, 다음에 잡게되는 가방은 전에 골랐던 보석을 모두 넣을 수 있으로 나머지 보석들 중 넣을 수 있는 보석들을 추가로 골라줄 수 있었다. 즉, 정렬을 통해 매번 보석을 전부 순회하지 않아도 됐다. 정렬에 사용되는 sort 함수는 시간복잡도가 O(NlogN)이므로 TLE가 나지 않아 적합했다.

 

이제 고른 보석들 중 가치를 기준으로 내림차순을 해줘야했는데, 이걸 가방을 순회하면서 같이하게되면 O(K*NlogN)이므로 처음에 떠올린 해법보다 더 나빴다.

 

이는 우선순위 큐를 사용해서 해결했다. 우선순위 큐가 보석의 가치를 기준으로 오름차순으로 정렬하면, 큐의 맨 위에있는 보석만 가져가면 됐기 때문이다.

 

따라서 가방을 하나 잡게되면, 그 가방의 무게를 초과하지 않는 보석들의 가치를 우선순위 큐에 넣어준다. 이후 큐의 맨 위에있는 보석을 가방에 넣는다. 다음 가방에서는 넣지 않은 보석들 중, 가방에 넣을 수 있는 보석들을 추가로 넣고 큐에서 빼는 짓을 계속해주면 된다.

 

다음은 전체 코드이다.

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

typedef pair<int, int> pii;

priority_queue<int> pq;
const int MAX = 3e5;
pii ice[MAX];
int bag[MAX];
int N, K;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> K;
	for(int i=0; i<N; i++) cin >> ice[i].first >> ice[i].second;
	for(int i=0; i<K; i++) cin >> bag[i];
	
	sort(ice, ice+N);
	sort(bag, bag+K);
	
	long long ret = 0;
	int idx = 0;
	for(int i=0; i<K; i++) {
		while((idx < N) && bag[i] >= ice[idx].first) pq.push(ice[idx++].second);
		if(pq.size()) {
			ret += pq.top();
			pq.pop();
		}
	}
	
	cout << ret << "\n";
}