[BOJ] 1202

보석 도둑

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

분류

• Gold 2

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

해법

모든 보석을 가격이 높은 순으로 정렬되도록 해줍니다.

보석을 비싼 순으로 하나씩 꺼내보면서
보석을 담을 수 있는 가방 중 가장 최대 무게가 작은 가방을 골라주면 됩니다.

정답 코드

/*
BOJ 1202: 보석 도둑
*/

#include <bits/stdc++.h>
#define V   first
#define W   second
using namespace std;

int n, k;
priority_queue<pair<int, int>> pq;
map<int, int> m;
int w, v;
int c;
long long res;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        pq.push({v, w}); // 비쌀수록 top에
    }
    while (k--) {
        cin >> c;
        m[c]++;
    }
    while (!pq.empty()) {
        pair<int, int> cur = pq.top();
        pq.pop();
        auto it = m.lower_bound(cur.W);
        if (it == m.end()) continue;
        res += cur.V;
        if (--it->second == 0) {
            m.erase(it);
        }
    }
    cout << res;
    return 0;
}