[백준] 보석 도둑

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

1202번: 보석 도둑

우선 문제부터 간단하게 요약하면,

 

보석점을 상덕이가 털려고 하는데, 상덕이가 가진 가방에는 각각 보석 1개씩만을 넣을 수 있고, 각각의 가방은 담을 수 있는 보석의 최대 무게를 가지고 있습니다. 이 때, 훔쳐갈 수 있는 보석의 최대 가격을 구하는 것이 문제입니다. 

 

<Solution>

우선 어떤 가방이 좋은 가방일지 생각을 해보면, 당연히 무게를 많이 담을 수 있는 가방이 좋은 가방이라고 할 수 있을 것입니다. 왜냐하면, 담을 수 있는 보석의 종류가 더 많을 것이기 때문입니다.

 

그러면, 당연히 담을 수 있는 무게가 작은 가방 부터 채워 나가야 할 것을 알 수 있습니다. 이제 알고리즘을 정리 해 보면, 

1. 보석과, 가방을 무게를 기준으로 오름차순 정렬 합니다. 2. 가방에 대해, 가방 무게 이하의 보석들의 가격을 모두 priority queue에 넣습니다. 3. priority queue 의 가장 위의 원소가 해당 가방에 들어가야 최대 금액을 훔칠 수 있습니다.  4. 2번과 3번 과정을 각각의 가방들에 대해 반복합니다. 이 때, 이미 넣은 보석들 다음 보석부터 매번 넣습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

int N, K;
int C[300000+10];

pair<int, int> jewels[300000+10];
priority_queue<int> pq; // to save value

long long solution(){
    long long ret = 0;
    // sort C
    sort(C, C+K);
    // sort jewels by M
    sort(jewels, jewels+N);
    // for every C iterate
    int index = 0;
    for(int i = 0; i<K; i++){
        // iterate through jewels
        for(; index<N; index++){
            if(jewels[index].first > C[i]) break;

            pq.push(jewels[index].second);
        }

        if(!pq.empty()){
            ret+=pq.top();
            pq.pop();
        }
    }

    return ret;
}


int main(){
    // getinput 
    cin >> N >> K;
    for(int i = 0; i<N; i++){
        cin >> jewels[i].first >> jewels[i].second;
    }
    for(int i = 0; i<K; i++){
        cin >> C[i];
    }

    cout << solution() << endl;
    return 0;
}