[백준 문제풀이] 1202 c++ 보석도둑

 

정렬을 활용하여 그리디 하게 풀 수 있는 문제.

 

1. 보석과 가방을 무게를 기준으로 오름차순 정렬

- 보편적인 그리디+정렬 문제는 무게를 기준으로 내림차순 정렬하여 가방을 채워나갈 수 있지만, 

 이 문제에서는 최적의 값을 찾지 못한다. 

 가장 낮은 무게의 가방을 기준으로 가장 높은 가치의 보석을 담는 것이 핵심

 

2. 우선순위 큐 자료구조를 활용하여 제한된 크기의 가방에 넣을 수 있는 무게의 보석을 다 담는다

 

담은 후 우선순위 큐가 가장 큰 값을 top에 위치할 것이므로 그 값을 i 번째 가방의 값으로 지정한다.

 

i+1 가방의 값도 마찬가지로 정할 수 있다. i 번째 가방에서 우선순위 큐에 넣었던 값들과 비교하여

제한된 무게에 들어가는 가장 큰 값을 구할 수 있다.

 

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

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, k;
	std::cin >> n >> k;

	std::vector<std::pair<int, int>> gem(n, {0,0});
	std::vector<int> bag(k, 0);

	int a, b;
	for (int i{ 0 }; i < n; i++) {
		std::cin >> a >> b;
		gem[i].first = a;
		gem[i].second = b;
	}
	for (int i{ 0 }; i < k; i++) {
		std::cin >> bag[i];
	}

	std::sort(gem.begin(), gem.end());
	std::sort(bag.begin(), bag.end());

	int j = 0, i = 0;
	long long ans = 0;
	std::priority_queue<int> q;
	
	for (int i{ 0 };i<k;i++) {
		while (j < n && bag[i] >= gem[j].first) {
			q.push(gem[j++].second);
		}
		
		if (!q.empty()) {
			ans += q.top();
			q.pop();
		}
	}
	std::cout << ans << "\n";
}