보석 도둑 C++ - 백준 1202

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

그리디 문제.

문제 접근

보석의 가격을 최대로 하여 담으려면,

1. 모든 가방에 최대한 담는다.
2. (반례가 있는 그리디한 방법)(1번을 충족시키기 위해)
현재 가방에 최대 무게를 담는다.
3. 1,2번을 지키며 가장 비싼 것을 고른다.

처음에는 되게 복잡하게 생각했었는데, 사실 간단한 방식이 있었다.

핵심은 아래와 같다.

가방의 최대 무게를 정렬해서 배열했을 때 $i$번째 가방은

항상 $i-1$번째 가방이 담을 수 있는 것을 담을 수 있다.

$i-1$번째 가방이 담을 수 있는 최대 무게 선안에서 모두를

우선순위큐에 내림차순으로 넣어놓고, 그 중 가장 큰 값을 꺼내며 가면

최적해를 보장할 수 있다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,k;
long long ans=0;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    vector<pair<int, int>> jw(n);
    vector<int> bp(k);
    priority_queue<int> pq;
    for(int i=0;i<n;i++) cin >> jw[i].first >> jw[i].second;
    for(int i=0;i<k;i++) cin >> bp[i];
    sort(bp.begin(), bp.end());
    sort(jw.begin(),jw.end(),[](pair<int, int> l, pair<int, int> r)->bool{return l.first<r.first;});
    int ind=0;
    for(int i=0;i<k;i++){
        while(ind<n){
            if(jw[ind].first<=bp[i]){
                pq.push(jw[ind].second);
                ind++;
            }
            else break;
        }
        if(!pq.empty()){
            ans+=pq.top();
            pq.pop();
        }
    }
    cout << ans;
    return 0;
}