[백준] 1202번 : 보석 도둑 (그리디 알고리즘) C++ 풀이

접근:

가방에는 무조건 1개만 넣을 수 있고, 최대한 넣었을 때 가장 가치가 높은 거를 넣어야 하는데,

가방 중에 가장 작은 가방에 들어갈 정도의 보석이라면, 다른 가방에는 무조건 들어갈 수 있게 된다.

 

 

전략:

가방과 보석을 크기 오름차순으로 정렬을 한다.

모든 가방을 조사하면서, 이 가방에 들어갈 수 있는 보석을 모두 꺼내어 놓은 뒤, 이 중 가장 가치 있는 것을 넣어서

하나 씩 가방을 채운다. 그렇게 되면, 들어갈 수 있는 가방 중에 가장 가치 있는 것 부터 넣을 수 있게 된다.

이때, 우선순위 큐를 이용하면, 가방에 들어갈 수 있는 보석 중에 가장 가치 있는 것을 선택하기 수월하다.

각 보석은 조사할 때 한 번 우선순위 큐에 들어간 보석은 더는 조사하지 않는다. 이유는 우선순위 큐의 성질에 의해서 가장 가치가 있는 것을 알아서 선택해주기 때문에 굳이 따로 조사할 필요가 없기 때문

 

구현:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int n,k;
vector<pii> jew;
priority_queue<int> pq; //보석
vector<int> inven;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    jew.resize(n);
    inven.resize(k);

    for(int i=0;i<n;i++){
        cin >> jew[i].first >> jew[i].second;
    }
    for(int i=0;i<k;i++){
        cin >> inven[i];
    }
    sort(inven.begin(), inven.end());
    sort(jew.begin(), jew.end());
    
    int idx = 0;
    long long result = 0;

    for(auto c : inven){
        while(idx < n && c >= jew[idx].first){ //가장 작은 가방에 들어갈 정도면 그 뒷 가방도 다 가능
            pq.push(jew[idx++].second);
        }

        if(!pq.empty()){ // 가능 한 것 중에서 가장 가치가 큰 것부터
            result += pq.top(); pq.pop();
        }
    }
    cout << result << '\n'; 
    return 0;
}