백준 1202. 보석 도둑 (그리디, 이진검색트리)

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

1202번: 보석 도둑

풀이는 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/solutions/1202.cpp  에서 가져왔다. 

 

1. 특징

1) 그리디

2) 정렬 

3) 이진검색트리 - set, multiset, map

 

2. 구현 포인트

**그리디 아이디어를 떠오르는게 중요하다 
-> 가장 가격이 높은 보석부터 확인하며 해당 보석을 담을 수 있는 가방 중

최대 무게가 가장 작은 가방을 이용해 보석을 담는게 이득이다. 

 

또한 문제에서 정렬에 대한 개념이 필요해서 해시(unoredred_multiset)가 아니라 이진검색트리(multiset)를 사용해야한다. 

그리고 중요한게 multiset에서 lower_bound의 의미를 아는 것이다. 

lower_bound(n)는 multiset에서 오름차순 정렬을 해치지않으면서 n을 넣을 수 있는 가장 첫번째 인덱스 반환한다. (multiset에서 찾은 n의 첫번째 값의 인덱스)

 

참고로 upper_bound(n)은 multiset에서 오름차순 정렬을 해치지않으면서 n을 넣을 수 있는 가장 마지막 인덱스를 반환한다. 

다시말해 multiset에서 찾은 n의 마지막 값의 인덱스 + 1 

 

시간복잡도: 이 문제는 1 <= n, k <= 300,000이다. 밑에 작성한 코드는 O(nlogc)의 풀이법이다. 

 

 

코드는 아래와 같다. 

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

//그리디
//가장 가격이 높은 보석부터 확인하며 해당 보석을 담을 수 있는 
//가방 중 최대 무게가 가장 작은 가방을 이용해 보석을 담는게 이득이다. 
int n, k;
pair<int, int> jewel[300002]; //무게 가격
multiset<int> bag; //무게가 중복될 수 있음
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    //정렬의 편의를 위해 무게/가격을 반대로 입력받음
    for(int i = 0; i < n; i++)
    {
        //가격, 무게
        cin >> jewel[i].second >> jewel[i].first;
    }
    sort(jewel, jewel+n); //first 기준 오름차순, 그 다음에 second 기준 오름차순

    for(int i = 0; i < k; i++)
    {
        int c;
        cin >> c;
        bag.insert(c);
    }

    long long ans = 0;

    for(int i = n-1; i >= 0; i--)
    {
        int m, v;
        tie(v, m) = jewel[i];
        auto it = bag.lower_bound(m); //해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 가방
        if(it == bag.end()) continue; // 최대 무게가 m이상인 가방이 없다
        ans += v;
        bag.erase(it);
    }
    cout << ans;
}