C++ 백준 1202 (보석 도둑)

백준 1202 (보석 도둑)

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

1202번: 보석 도둑

---

정렬과 우선순위큐를 이용해 풀 수 있는 문제였다.

 

설명

---

우선 가방의 크기를 오름차순으로 정렬한다. => 담긴 vector를 bag이라고 하겠다.

 

또한 보석의 pair를 무게에 대한 오름차순으로 우선순위 큐에 저장한다. => 해당 큐를 jew라고 하겠다.

 

준비를 마친 후 과정은 다음과 같다.

정렬된 가방의 크기를 저장한 배열을 돌며 현재 가방의 크기보다 작거나 같은 jew에 담긴 보석들을 가치순으로 새로운 우선순위 큐에 저장한다. => 해당 큐를 tmp라고 하겠다.

 

jew에는 보석이 무게순으로 들어가있으므로 현재 가방의 크기보다 jew의 top위치에 있는 보석의 무게가 크다면 그냥 멈추고 다음 가방으로 넘어가면 된다.

 

각 현재 가방의 크기에서 넣을 수 있는 모든 보석을 넣었다면 tmp에는 가치순으로 보석이 정렬되어 있으므로 가장 위에있는 보석을 하나 꺼내면 된다.

 

구현

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
using namespace std;

priority_queue <pii> tmp;
priority_queue <pii, vector<pii>, greater<pii>> jew;
vector <int> bag;
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,k,a,b;
    
    long long ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        jew.push({a,b});
    }
    for(int i=0;i<k;i++){
        cin>>a;
        bag.push_back(a);
    }
    sort(bag.begin(), bag.end());
    for(int i=0;i<k;i++){
        int curr = bag[i];

        while(!jew.empty()){
            if(jew.top().first>curr) break;
            tmp.push({jew.top().second, jew.top().first});
            jew.pop();
        }
        if(tmp.empty()) continue;
        ans+=tmp.top().first;
        tmp.pop();
    }
    
    cout<<ans;
    return 0;
}