[백준 C++] 1202번 보석 도둑

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

입력 2 1 5 10 100 100 11 출력 10

## 풀이
그리디하게 풀수 있다. 보석가치가 높은 순으로 접근해서 그 보석을 담을 수 있는 가방중에 가장 작은 크기의 가방에 담는다. 이를 반복한다.

찾아보니 더 쉽게 풀 수 있는 방법이 있었다. 보석과 가방을 모두 무게가 낮은 순으로 정렬 하고, 가방을 기준으로 for문을 돌린다. 가장 낮은 가방부터 들어갈 수 있는 모든 보석을 우선 순위 큐에 넣는다. 그 후 가장 가치가 큰 보석을 삭제하고 가치를 결과값에 더한다. 이후 다음가방으로 접근하고 방금 사용했던 우선 순위 큐에 추가로 더 들어갈수 있는 보석을 넣고 이전 과정들을 반복한다. 접근횟수가 적어 시간초과가 걸릴 확률이 더 적다.

## 어려웠던 점
일단 역시나 long long에서 한번 틀려줬다. 출력이 int범위를 넘을 수 있다. 그다음 발목을 잡은 것은 시간 초과 였다. 처음에는 보석과 가방을 단순히 벡터로 정의하고 정렬을 한 다음 이진 탐색으로 접근하였는데 시간초과가 났다. 정렬도 시간이 오래 걸리고 가방을 사용할때마다 벡터에서 지워줘야 하는데 거기서도 시간이 오래 걸린 것 같다. 그래서 보석은 우선 순위 큐로 대체하였고 가방은 multiset자료형으로 대체하였더니 통과하였다.

## 배운 점 / 느낀 점
처음에 dp문제인줄 알았는데 아니었다.
multiset자료형을 처음 써봤는데 매우 좋은것 같다. 삭제 속도도 빠르고 자동으로 정렬도 되고. 앞으로 삭제가 많은 문제를 풀때 자주 애용할 것 같다. 

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

int n, k;
long long rr;
priority_queue<pair<int,int>> ju;
multiset<int> bag;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;
    ju = priority_queue<pair<int,int>>();
    bag = multiset<int>();

    for (int i = 0; i < n; i++) {
        pair<int,int> ttt;
        cin >> ttt.second >> ttt.first;
        ju.push(ttt);
    }
    for (int i = 0; i < k; i++) {
        int t;
        cin >> t;
        bag.insert(t);
    }

    while(!ju.empty()){
        pair<int,int> juu = ju.top();
        ju.pop();

        auto mid = bag.lower_bound(juu.second);
        if(mid == bag.end()){
            continue;
        }
        else{
            rr+=juu.first;
            bag.erase(mid);
        }
    }
    cout << rr;
    return 0;
}