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

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

1202번: 보석 도둑

---

보석 도둑 문제는 이진검색트리를 이용하여 해결할 수 있습니다.

 

훔칠 수 있는 보석의 가격을 구해야하는데, 가방에는 최대 한 개의 보석만 넣을 수 있습니다. 

가방에 넣을 수 있는 보석 중 가장 가치가 큰 것을 선택하면 됩니다. 

그럼 어느 가방에 먼저 넣어야할까요?

 

아래 예에서, 가방에 담을 수 있는 최대 무게가 가장 무거운 가방부터 넣어보겠습니다. 

	최대 무게
가방 1	10
가방 2	100

	무게	가치
보석 1	5	100
보석 2	100	5

 

1. 가방 2에 넣을 수 있는 보석 중 가치가 가장 높은 보석 1을 넣는다.
2. 가방 1에 보석 2를 넣을 수 없다.
3. 보석의 최대 가격은 100.

다음으로, 최대 무게가 가장 가벼운 가방부터 넣어보겠습니다.

1. 가방 1에 넣을 수 있는 보석 중 가치가 가장 높은 보석 1을 넣는다.
2. 가방 2에 넣을 수 있는 보석 중 가치가 가장 높은 보석 2를 넣는다.
3. 보석의 최대 가격은 105이다.

이처럼 가방 A, B가 있을 때, 가방에 넣을 수 있는 최대 무게가 B가 더 크다면,

가방 A에 넣을 수 있는 보석은 가방 B에 넣을 수 있지만,

가방 B에 넣을 수 있는 보석은 가방 A에 넣을 수 없기 때문에 

최대 무게가 가장 가벼운 가방부터, 가치가 높은 보석을 넣어야, 훔칠 수 있는 보석의 가치를 최대로 만들 수 있습니다.

 

알고리즘은 아래와 같습니다.

1. 보석을 모두 Gems 이진 검색 트리에 넣는다. 
2. 가방을 모두 bags 배열에 넣는다.
3. 가방을 최대 무게를 기준으로 오름차순 정렬한다.
4. 가벼운 가방부터 다음 과정을 진행한다. 
   1. 가방에 담을 수 있는 보석을 모두 Gems에서 제거하고, Avail 이진 검색 트리에 넣는다.
   2. Avail 이진 검색 트리에서 가치가 가장 높은 보석을 제거한다.
   3. 해당 보석의 가치를 더해준다.

 

이진 검색 트리를 사용한 이유는 원소가 정렬되어 저장되며, 삽입, 삭제를 O(log N)에 수행할 수 있기 때문입니다.

또한, 굳이 제거된 보석을 Avail에 넣어주는 이유는, Gems가 보석의 무게를 기준으로 정렬되어 있기 때문에 Avail에 넣어 보석의 가치를 기준으로 정렬하고, 그 중 최대값을 추출하기 위해서 입니다.

 

bags가 최대 무게를 기준으로 오름차순 정렬되어 있기 때문에 이전 단계에서 Avail에 삽입된 보석은 다음 단계에서도 가방에 넣을 수 있습니다. 

 

⚠️ 단,  가방의 최대 무게와 보석의 {무게, 가격}은 중복될 수 있으므로, multiset을 사용해야합니다.

 

아래는 전체 코드입니다. 

 

#include <bits/stdc++.h>
using namespace std;

#define w first
#define v second
#define MAX 300010

multiset<pair<int, int>> gems;
multiset<int> avail; 
int bags[MAX];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;

    // 가장 가벼운 무게를 담을 수 있는 가방부터
    // 넣은 수 있는 보석 중 가장 가치가 큰 보석을 넣음
    for(int i = 0; i < n; i++){
        pair<int, int> gem;
        cin >> gem.w >> gem.v;
        gems.insert(gem);
    }

    for(int i = 0; i < k; i++) cin >> bags[i];  // 각 가방에 넣을 수 있는 최대 무게를 입력 받음
    
    sort(bags, bags + k);   // 가방을 오름차순 정렬

    long long ans = 0;

    for(int i = 0; i < k; i++){
        int cap = bags[i];  // 가방에 담을 수 있는 최대 무게
        auto upper = gems.upper_bound({cap, INT_MAX});  // 가방에 담을 수 있는 보석의 무게보다 무거운 보석 중에서 가장 가벼운 보석의 위치
        
        for(auto iter = gems.begin(); iter != upper;){  // 각 보석을 gems에서 제거하고, avail 이진 검색 트리에 삽입
            avail.insert((*iter).v);   // 단, 보석의 가치를 기준으로 정렬되도록 가치를 첫번째로 넣어줌
            iter = gems.erase(iter); // 보석을 gems에서 제거
        }

        if(avail.size() > 0){
            int m = *prev(avail.end());     // 넣을 수 있는 보석 중 가장 가치가 높은 보석을 가방에 넣음
            avail.erase(prev(avail.end())); // 해당 보석을 삭제
            ans += m;   // 제거된 보석의 가치를 더해줌
        }
    }

    cout << ans << "\n";
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

1 1
100 100
10
-> 0

4 3
1 1
1000000 100000000
1000000 100000000 
1000000 100000000
1000000 1000000 1000000
-> 300000000