[백준] 그리디 - 1202. 보석도둑

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

예제 입력1

3 2
1 65
5 23
2 99
10
2

 

예제 출력1

164

 

생각

그리디 알고리즘 정리를 해보고 나서 푸는 건데도 생각을 구현으로 옮기는 것이 쉽지가 않음을 느꼈다. 입력 받는 거는 무리없이 받았지만 가방의 무게가 여러개로 주어진다는 점이 까다로웠다. 조건이 많다보니 어떻게 풀어나가야할지 감을 잡기가 힘들어서 다른 풀이를 참고했다. 우선순위 큐 문제를 풀고나서 봐서 그런지 이전보다 간단하게 느껴졌다. 반복적인 풀이가 필요할 것같다. 완전히 이해가 되면 추후에 정리할 예정

 

작성한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int W[300001];

int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    vector<pair<int, int> > v;
    
    int n, k; //n:보석 개수, k:가방 개수
    cin >> n >> k;
    
    for(int i=0; i<n; i++) {
        int w, p; // w:보석 무게, p:보석 가격
        cin >> w >> p;
        v.push_back(make_pair(w,p));
    }
    
    for(int i=0; i<k; i++){
        cin >> W[i]; //가방의 무게
    }
    
    sort(v.begin(), v.end());
    sort(W, W+k);
    
    priority_queue<int> pq;
    
    int j=0;
    long long int sum=0;
    
    // 무게가 낮은 가방부터
    for(int i=0; i< k; i++){
        while(j<n && v[j].first <= W[i]){ //보석무게가 가방무게보다 작아야한다는 조건을 만족하면
            pq.push(v[j].second); // 보석 가격 넣어준다
            j++;
        }
        if(!pq.empty()){
            sum += pq.top();
            pq.pop();
        }
    }
    
    cout << sum << "\n";
    return 0;
}