BOJ 1202 : 보석 도둑

풀이 요약

그리디

풀이 상세

1. 보석과 가방을 모두 오름차순 정렬한다.

2. 현재 가방 무게에서 담을 수 있는 모든 보석을 우선순위 큐에 담은 후, 가장 큰 보석을 뽑아내자. 이를 반복하여 총 K 개의 최대 보석 무게를 찾는다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, K;
vector<int> b;
vector<pair<int, int>> j;
long ans;

void input() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> K;
    int n1,n2;
    for(int i=0; i<N; i++) {
        cin >> n1 >> n2;
        j.push_back({n1,n2});
    }
    for(int i=0; i<K; i++) {
        cin >> n1;
        b.push_back(n1);
    }
    sort(j.begin(), j.end());
    sort(b.begin(), b.end());

}

void solve() {
    int idx = 0;
    priority_queue<int> pq;
    for(int i=0; i<K; i++) {
        while(idx<N && j[idx].first<=b[i]) pq.push(j[idx++].second);
        if(!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve();
    output();
}