[백준] 1202 보석도둑 (Greedy Algorithm)

How to solve

*priority queue 를 사용!

1. jewerly를 보석 무게 기준 기준 오름차순 정렬합니다.

2. 가방을 작은것 부터 채우기 위해 오름차순 정렬합니다.

3. K개의 가방을 차례로 채웁니다.

4. 가방의 무게보다 작은 주얼리는 모두 priority queue(pq)에 넣어줍니다.

5. 넣은 주얼리 중 가장 비싼 주얼리(pq에 내림차순으로 정렬되어있으므로 pq.top())를 선택합니다.(res에 더해줌)

6. 넣은 주얼리를 pop하고, 다음 가방을 채웁니다.

---

Problem

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

9203

2203

1562

23.753%

문제

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

상덕이가 털 보석점에는 보석이 총 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

 

---

Solution

#include <bits/stdc++.h>
#include <iostream>

#define int long long

using namespace std;

int N, K;
int res = 0;
vector<pair<int, int> > jewelry;
vector<int> bag;
priority_queue<int> pq;

void input_data(){
    cin >> N >> K;
    for(int i=0; i<N; i++){
        int a, b;
        cin >> a >> b;
        jewelry.push_back({a, b});
    }
    for(int i=0; i<K; i++){
        int a;
        cin >> a;
        bag.push_back(a);
    }
}

signed main(){
    input_data();

    //sort jewrly
    sort(jewelry.begin(), jewelry.end());
    //sort bag
    sort(bag.begin(), bag.end());

    //k개의 가방을 차례로 채움
    int j = 0;
    for(int i=0; i<K; i++){
        while(j<N && jewelry[j].first <=bag[i]){
            //가방의 무게보다 작은 주얼리 pq에 push
            pq.push(jewelry[j].second);
            j++;
        }
        //최대 값을 넣어주고 pq에서 pop
        if(!pq.empty()){
            res += pq.top();
            pq.pop();
        } 
    }
    cout << res << endl;
    return 0;
}