[Algorithm] 1202: 보석 도둑

📦1202: 보석 도둑

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-18
문제 확인하기

풀이

• 가방 안에만 들어가면 되기 때문에 가방 안에 들어가는 무게를 가진 보석들을 전부 우선순위 큐에 넣는다.
• 우선순위 큐는 가격이 높은 순을 기준으로 정렬하고 가방 개수만큼 뽑아낸다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'
using namespace std;
 
int N, K;
long long res=0;
pair<int, int> jewelry[300001];
int bag[300001];
priority_queue<int> pq;
 
void Input(){
    cin >> N >> K;
    for(int i=0; i<N; i++){
        int m, v;
        cin >> m >> v;
        jewelry[i] = make_pair(m, v);
    }
    for(int i=0; i<K; i++){
        cin >> bag[i];
    }
}
 
void Solution(){
    sort(jewelry, jewelry+N);
    sort(bag, bag+K);
 
    int j = 0;
 
    for(int i=0; i<K; i++){
        while(j < N && bag[i] >= jewelry[j].first){
            pq.push(jewelry[j].second);
            j++;
        }
        if(!pq.empty()){
            res += pq.top();
            pq.pop();
        }
    }
    cout << res << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}