[Baekjoon] 1202번: 보석 도둑

🥅 문제

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

 

🔍 설계

가방에는 가방이 담을 수 있는 무게 이하의 보석만 담을 수 있다. 보석을 어떻게 담을지가 문제다.

 

보석과 가방의 무게를 오름차순으로 정렬하고, 가방마다 담을 수 있는 보석 중 최대 가치를 결과에 더하면 된다.

 

최대 가치는 우선순위 큐를 이용하여 구한다. 탐색하는 보석에 대하여 인덱스를 공유하면, O(N+K)로 해결할 수 있고, 우선순위 큐를 공유함으로써 그 가방 최대 무게 이하의 보석을 고려할 수 있다.

 

👊 풀이

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

int n, k, m, v, c, p = 0;
long long result = 0;

vector<pair<int, int>> jewel;
vector<int> bag;
priority_queue<int> possible;

int fillBag(int bag_idx) {
	while (p < n && jewel[p].first <= bag[bag_idx]) {
		possible.push(jewel[p++].second);
	}
	if (possible.empty()) {
		return 0;
	}
	else {
		int value = possible.top();
		possible.pop();
		return value;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> m >> v;
		jewel.push_back({ m, v });
	}
	for (int i = 0; i < k; i++) {
		cin >> c;
		bag.push_back(c);
	}

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

	for (int i = 0; i < k; i++) {
		result += fillBag(i);
	}

	cout << result << "\n";
	return 0;
}