C++ / 백준 / 1202 / 보석 도둑

문제

 

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

1202번: 보석 도둑

 

 

 

문제풀이

 

처음에는 보석의 가격이 큰 순, 가격이 같다면 무게는 작은 순, 가방의 무게는 큰 순으로 정렬해서 풀어보려 했지만 시간초과, 틀렸습니다를 겪고 방법을 바꿔보았다.

 

가방과 보석을 모두 오름차순으로 정렬하고, 가방에 담을 수 있으면 우선순위 큐에 다 집어넣는다.

보석이 더 무거워서 담을 수 없으면, 우선순위 큐에서 우선순위가 가장 높은 보석을 가방에 넣고 다음 가방으로 넘어간다.

(우선순위 큐에 값을 넣을 때, 보석의 무게는 이미 위에서 판별했으므로 무시하고 가격의 정보만 넣으면 된다.)

모든 가방을 탐색할 때까지 위의 작업을 반복한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<int, int>
using namespace std;

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

	int N(0), K(0);
	cin >> N >> K;

	priority_queue<int>pq;
	vector<pii>jewel(N, { 0,0 });
	vector<int>bag(K, 0);

	for (int idx = 0; idx < N; ++idx) {		
		cin >>jewel[idx].first >> jewel[idx].second;
	}
	for (int idx = 0; idx < K; ++idx) {
		cin >> bag[idx];
	}

	sort(bag.begin(), bag.end());
	sort(jewel.begin(), jewel.end());

	int jewel_idx(0);
	ll answer(0);
	
	for (int idx = 0; idx < K; ++idx) {
		for (jewel_idx; jewel_idx < N; ++jewel_idx) {
			if (bag[idx] >= jewel[jewel_idx].first) {
				pq.push(jewel[jewel_idx].second);
			}
			else break;
		}
		if (pq.empty()) continue;
		answer += pq.top();
		pq.pop();
	}
	

	cout << answer;
}