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

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

1202번: 보석 도둑

문제 풀이

가방에 최대 1개의 보석밖에 못 넣기 때문에 그리디로 풀면 된다.

가방에 넣을 수 있는 보석들을 다 Priority_queue에 넣어놓고, 그리고 가방에 담을 수 있는 무게를 넘어가면 Priority queue에서의 Top에 있는 걸 sum에 합치고 다음 가방으로 넘어가는 형식으로 해결한다.

소스 코드

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

int n, k;
pair<int, int> v_jewerly[300001];
int v_bag[300001];
priority_queue<int> pq;

int main() {
	cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> v_jewerly[i].first >> v_jewerly[i].second;
    }
    for (int i = 0; i < k; ++i) {
        cin >> v_bag[i];
    }
    
    sort(v_jewerly, v_jewerly + n);
    sort(v_bag, v_bag + k);

    int idx = 0;
    long long sum = 0;

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