[BOJ 1202] 보석 도둑(C++)

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

1202번: 보석 도둑

 

#include <bits/stdc++.h>
using namespace std;
 
struct compare{
    bool operator()(pair<long long,long long> a, pair<long long,long long> b){  //가격별 내림차순
        return a.second < b.second;
    }
};
 
bool comp(pair<long long,long long> a, pair<long long,long long> b){    //무게순 정렬(오름차순)
    return a.first < b.first;
}
 
int main(){
    long long N,K;
    long long M,V,C;
    long long ans=0;
    cin>>N>>K;
    vector<pair<long long, long long> > jewels;
    vector<long long> bags;
    priority_queue<pair<long long,long long>, vector<pair<long long,long long> >, compare> pq;
    for (long long i=0; i<N; i++){
        cin>>M>>V;
        jewels.push_back(make_pair(M,V));
    }
    for (long long i=0; i<K; i++){
        cin>>C;
        bags.push_back(C);
    }
    sort(bags.begin(), bags.end());
    sort(jewels.begin(), jewels.end(), comp);
    long long count=0;
    for (long long i=0; i<K; i++){
        while(true){
            if (count>=N || jewels[count].first>bags[i]){       //무게 넘치면
                break;
            }
            pq.push(jewels[count]);
            count++;
        }
        if (!pq.empty()){
            ans+=pq.top().second;
            pq.pop();
        }
    }
    cout<<ans<<endl;
}

우선순위 큐를 이용하는 문제.

일단 보석을 무게 오름차순으로 정렬한다.

가방도 무게 오름차순으로 정렬한다.

priority queue 를 만들어서, 가방을 하나씩 선택할때마다 가방에 들어갈 수 있는 모든 보석을 큐에 집어넣는다.

큐의 compare 함수는 무게순으로 지정해놓았다. 즉 무게가 무거울수록 큐의 맨 앞에 위치하게 되고 따라서 가능한 최대의 이득을 얻을 수 있다.

 

 아까 선택한 i번째 가방이 곧 선택할 i+1번째 가방보다 가벼우므로, 큐에 남은 애들을 i+1가 당연히 넣을 수 있다.

 

1) 우선순위 큐를 사용해서 최대의 이득을 취하기

2) 가방, 쥬얼리를 오름차순 정렬하기