[알고리즘/백준]1202_보석 도둑

알고리즘

무게별 가방 안에 들어갈 수 있는 보석들 중 가장 비싼 보석 하나를 담는다.

입력 값 : N(보석의 개수), K(가방의 개수) (0< N, K <300001)
다음 N 개의 줄에 각 보석의 정보 Mi(무게)와 Vi(가치)가 주어진다. (0< Mi, Vi <1000001)
다음 K 개의 줄에 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (10< Ci <100000001)

1번 가방이 들 수 있는 모든 보석중에 가치가 가장 높은 보석을 가방에 담는다. C1 = 2 이므로 1번과 2번 보석을 넣을 수 있다.
그 중에 2번 보석이 가장 가치가 높기 때문에 1번 가방에 2번 보석을 넣는다.

2번 가방의 경우에도 담을 수 있는 모든 보석의 가치를 비교해서 가장 가치가 높은 보석을 담는다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 300000;
int n, k;
int bag[MAX];
pair<int, int> jewelry[MAX];
priority_queue<int> pq;

int main(){
    long long answer = 0;
    cin >> n >> k;
    
    for(int i = 0 ; i<n ; i++){
        cin >> jewelry[i].first >> jewelry[i].second;
    }
    
    for(int i = 0 ; i<k ; i++){
        cin >> bag[i];
    }
    
    //무게를 기준으로 오름차순 정렬
    sort(jewelry, jewelry+n);
    sort(bag, bag+k);
    
    
    int index = 0;
    for(int i = 0 ; i<k ; i++){
    	//i번째 가방이 담을 수 있는 모든 보석을 최대힙에 담는다.
        while(index<n && jewelry[index].first <= bag[i]){
            pq.push(jewelry[index++].second);
        }
       
        if(!pq.empty()){
            answer += pq.top();
            pq.pop();
        }
    }
    cout << answer;
    return 0;
}