[백준] 1202번 보석 도둑

문제 링크: https://www.acmicpc.net/problem/1202

문제

입출력

문제 접근

greedy와 max heap을 사용하는 문제였다. greedy문제라는 건 알았는데, 어떻게 풀어야 될지 감이 안와서, 다른 사람이 푼 것을 보고 참고했다. 먼저 보석들을 크기별로 또 그 안에선 value가 높은 거 별로 sort를 해주고, 가방은 크기가 작은 거 별로 sort해준다.
그리고, 가방 작은 거부터 차례로 그 가방 안에 넣을 수 있는 보석들을 priority queue에 넣어주고, 다 넣는 것이 끝날 때마다 max_heap에 가장 top부분을 뽑아주고 더해준다.

코드 구현(c++)

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

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first) return a.second > b.second;
    else return a.first < b.first;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    priority_queue<int> pq;
    vector<pair<int, int> > v;
    vector<int> v_bag;
    int N, K;
    cin >> N >> K;
    int temp_weight, temp_value;
    for(int i = 0 ; i < N ; i++){
        cin >> temp_weight >> temp_value;
        v.push_back(make_pair(temp_weight, temp_value));
    }
    for(int i = 0 ; i < K ; i++){
        cin >> temp_weight;
        v_bag.push_back(temp_weight);
    }
    sort(v.begin(), v.end(), cmp);
    sort(v_bag.begin(), v_bag.end());
    int idx = 0;
    long long result = 0;
    for(int i = 0 ; i < K ; i++){
        while(idx < N && v[idx].first <= v_bag[i]){
            pq.push(v[idx].second);
            idx++;
        }
        if(!pq.empty()){
            result += pq.top();
            pq.pop();
        }
    }
    cout << result << "\n";
}