BOJ 1202 보석 도둑

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

웰노운이라 예전부터 풀고 싶은 문제였는데, knapsack DP로 접근하다가 잘 안돼서 놔두었던 문제입니다.

 

결국 바킹독님의 이진검색트리 알고리즘 강의를 듣고 해결하였습니다.

지금까지 C++에서 set 자료구조를 쓰면서 lower/upper_bound 함수를 쓸 수 있는 지 몰랐는데, 이 기능이 된다는 것을 배우고 난 뒤에 이를 많은 문제에 유용하게 적용할 수 있겠다고 느꼈습니다.

 

 

풀이)

그리디한 전략 : 가치가 가장 높은 보석부터, 그 보석을 담을 수 있는 가방이 있다면 용량이 가장 적은 가방에 넣는다.

 

 

 

귀류법을 통한 증명
1. 그러한 보석을 용량이 가장 적은 가방이 아니라, 그 보석을 더 용량이 큰 가방에 넣는 경우가 더 이득인 경우가 있다.

-> 용량이 더 큰 가방에 담은 그 보석을, 용량이 가장 적은 가방으로 옮겨 담을 수 있다. 이때 용량이 가장 적은 가방에 이미 보석이 담겨있다면, 그 보석을 용량이 더 큰 가방에 마찬가지로 옮길 수 있으므로(가방 간 보석 교환), 용량이 더 큰 가방에 넣는 경우가 더 이득인 경우는 있을 수 없다.

 

2. 그러한 보석을 용량이 가장 적은 가방에 담지 않는 대신, 그냥 버리는 게 더 이득인 경우가 있다.

-> 용량이 가장 적은 가방에 이미 다른 보석이 담겨있다고 하자. 지금 우리는 가장 가치가 높은 보석 순으로 보고 있기 때문에, 해당 가방에 이 보석을 넣는 게 더 이득이다. 또한 그 가방에 보석이 담겨있지 않은 경우에도 당연히 이 보석을 넣는 게 더 이득이다.

 

 

각 보석에 대해, 그러한 가방이 무엇인지 빠르게 찾기 위해서 가방을 multiset으로 관리하는 것이 포인트입니다(용량이 같은 가방이 2개 이상 있을 수 있으므로 set으로는 안됩니다). 또한, 가장 가치가 높은 보석부터 가방을 고를 수 있게 하기 위해 보석은 우선순위 큐로 관리했습니다(코드에선 보석의 가치가 같을 경우 무게가 더 낮은 보석의 우선순위가 더 높지만, 그냥 가치만 가지고 정렬해도 됩니다).

 

 

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
multiset<ll> bag;

struct cmp{
    bool operator()(pll a, pll b){
        if(a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    }
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll N, K;
    cin >> N >> K;

    priority_queue<pll, vector<pll>, cmp> pq; // (가치, 무게).

    for(int i=1; i<=N; i++){
        ll M, V;
        cin >> M >> V;
        pq.push({V, M});
    }


    for(int i=1; i<=K; i++){
        ll k;
        cin >> k;
        bag.insert(k);
    }

    ll ans = 0;
    while(!pq.empty()){
        if(bag.empty()) break;
        
        ll j_val, j_size;
        tie(j_val, j_size) = pq.top();

        auto loc = bag.lower_bound(j_size);
        if(loc != bag.end()){
            ans += j_val;
            bag.erase(loc);
        }
        pq.pop();
    }
    cout << ans;
}