[C++] 백준 온라인 저지 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)

모든 숫자는 양의 정수이다.

 

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

풀이 과정

 

 우선순위 큐를 만들어서 보석 가격을 비싼 순서대로 정렬한 뒤 가방에 넣을 수 있는 무게를 비교해보며 합계를 구하면 될 것 이라 생각했는데 처음에는 가방 무게 배열을 벡터로 썼다가 보석을 넣을 수 있는 가방을 탐색하는 과정에서 시간 초과가 나서... 가방 무게 배열을 multiset으로 바꾸고 통과했습니다. 

* multiset : set과 같은데 중복 원소를 허용하는 set

 

1. key: 가격 value: 무게 pair 구조체를 저장하는 우선순위 큐를 만들어서 가격이 비싼 순서대로 정렬되도록 한다. 

 

2. 가방 무게를 입력받는 배열을 multiset으로 만든다. 가방 검색 시 효율을 높이면서 무게가 같은 가방이 여러 개 있을 수도 있기 때문에 multiset 사용.

 

3. 보석 큐가 비기 전 까지나 가방 배열이 비기 전 까지 top에 있는 보석의 무게보다 같거나 큰 가방이 가방 배열에서 lower_bound로 찾아지면 합계에 더하고 가방 배열에서 삭제한다. 이 때 std::lower_bound는 set.lower_bound보다 속도가 느려서 시간초과가 나니 꼭 set의 멤버함수로 포함되어 있는 lower_bound를 사용해야 한다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    
    priority_queue<pair<int, int>> gems;
    for (int i = 0; N > i; i++)
    {
        int weight, price;
        cin >> weight >> price;
        gems.emplace(make_pair(price, weight)); //key: 가격 value: 무게
    }
    
    multiset<int> bags;
    for (int i = 0; K > i; i++)
    {
        int weight;
        cin >> weight;
        bags.insert(weight);
    }
    
    long long answer = 0; //오버 플로우 방지용 
    while (!bags.empty() && !gems.empty())
    {
        auto gem = gems.top();
        gems.pop();
        
        //현재 가장 비싼 보석을 담을 수 있는 가방이 있으면 합계에 보석 가격을 더하고 해당 가방 삭제
        //lower_bound: 배열에서 인자값보다 같거나 큰 첫번째 원소를 찾아주는 함수 
        auto it = bags.lower_bound(gem.second);
        if (bags.end() != it)
        {
            answer += gem.first;
            bags.erase(it);
        }
    }
    
    cout << answer;
    
    return 0;
}