BOJ : 1202 보석 도둑

---

[BOJ 1202(G2) 리뷰]

상덕이에게는 가방이 K개가 있고 가방마다 담을 수 있는 무게가 다르다.
보석점에는 보석이 N개가 있고, 보석의 무게와 가격이 주어진다.
상덕이가 최대한 가격이 높은 보석들을 훔치려면 어떻게 해야 할까?

보석가격의 합이 최대가 되게하려면 다음과 같은 조건을 만족해야 한다.

• 가지고 있는 가방 K개를 다 사용해야 한다.
• 가방에 담을 수 있는 보석의 무게 중 가장 가격이 높은것을 훔쳐야 한다.

위와 같은 조건을 만족하며 보석을 훔치기 위해서는 먼저 가방의 무게를 오름차순으로 정렬해야 한다.
왜냐하면 가방에 담을 수 있는 무게가 높음에도 낮은 무게의 보석을 훔치게되면 낮은 무게를 담을 수 있는 가방이 가격이 높은 보석을 훔칠 수 없는 가능성이 생기기 때문이다.

예를들어 가방에 담을 수 있는 무게가 각각 2,5인 가방이 있고 보석은 [무게2,가격30], [무게4,가격20]이 있을때
5짜리 가방에 무게2짜리 보석을 담게되면 무게2짜리 가방은 아무 보석도 담을 수 없다.
따라서 무게가 낮은 가방부터 하나씩 보석을 담아야한다. 이때는 현재까지의 담을 수 있는 무게중 가격이 가장 높은 무게를 담으면 된다. 이 부분을 나는 우선순위 큐를 통하여 구현 했다. 

알고리즘은 다음과 같다.

• 먼저 보석의 무게,가격과 가방의 무게를 입력받은 후 둘 다 오름차순으로 정렬한다.
• 그후 무게가 적은 가방부터 하나씩 보석을 담는 과정을 수행할 것이다.
• 보석의 리스트를 처음부터 하나씩 살펴본다. 정렬되어 있으므로 가장 먼저 나오는 보석은 무게가 가장 낮은 보석일 것이다.
• 현재 보석이 현재 가방에 넣을 수 있는 보석이라면 우선순위 큐에 PUSH해준다. 이렇게 하면 우선순위 큐에는 현재까지 가방에 담을 수 있는 보석의 가격 중 가장 높은 가격이 TOP으로 오게 될 것이다.
• 만약 보석의 무게가 가방의 무게보다 큰 경우 우선순위큐에 넣는 과정을 중단하고 우선순위 큐의TOP값을 정답에 더해준 후 POP해준다.
  
  

위 과정을 가방의 갯수인 K번 반복하면 가방 K개에 넣을 수 있는 보석의 최대값을 구할 수 있다.

---

/*
    20.09.09
    BOJ : 1202 보석 도둑 (https://www.acmicpc.net/problem/1202)
    그리디
*/
#include <bits/stdc++.h>
using namespace std;

vector <pair<int,int>> price;
vector <int> bag;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        int M, V;
        cin >> M >> V;
        price.push_back({ M,V });
    }
   
    for (int i = 0; i < K; i++)
    {
        int input;
        cin >> input;
        bag.push_back(input);
    }

    sort(price.begin(), price.end());
    sort(bag.begin(), bag.end());

    priority_queue <int, vector<int>, less<int>> pq;
    long long int ans = 0;
    int idx = 0;
    for (int i = 0; i < K; i++)
    {
        int cur = bag[i];
        while (idx < N)
        {
            if (price[idx].first > cur) break;
            pq.push(price[idx].second);
            idx++;
        }
        if (!pq.empty())
        {
            ans += pq.top(); pq.pop();
        }
    }
    cout << ans;
}