백준

DP로 해결을 시도해 보았지만 결국 틀렸고 도무지 답이 생각나지 않아 해설을 찾아보게 되었다. 문제 해결을 우선 순위 큐를 이용해 해결하는 문제였고 앞으로 비슷한 유형의 문제가 나오면 같은 방식으로 쉽게 해결 할 수 있을 것 같다.

핵심은 가방과 보석을 오름 차순으로 정렬하고 가장 무게가 작은 가방부터 가능한 보석을 우선 순위 큐(오름 차순)에 넣어 가방에 넣을 수 있는 무게중 가장 무거운 것 부터 처리하는 것이였다.

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

using namespace std;

int n, k;

vector<pair<int,int>> jewelry;
vector<int> bag;
priority_queue<int, vector<int>, less<int>> pq;

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		jewelry.push_back({ a,b });
	}

	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		bag.push_back(a);
	}

	int idx = 0;
	long long sum = 0;

	//3 2
	//1 65
	//2 99
	//5 23

	//2
	//10

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

	for (int i = 0; i < k; i++) {
		while (idx < n && bag[i] >= jewelry[idx].first) {
			pq.push(jewelry[idx].second);
			idx++;
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}

	cout << sum;

	return 0;
}