BOJ 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)

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

출력

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

재정의와 추상화

이 문제는 STL의 multiset을 모른다면 꽤 애를 먹을 수 있는 문제이다. (자주 사용하는 STL 컨테이너는 다 외워두자..)

1. 입력받은 보석 정보는 보석의 가치에 대한 내림차순으로 우선순위 큐에 담아둔다.
2. multiset을 이용하여 가방의 최대 무게 정보를 저장한다. 이때, multiset의 특징에 따라 오름차순 정렬된다.
3. 우선순위 큐에 있는 원소가 하나도 없을 때까지 아래 과정을 진행한다.
   1. 우선순위 큐 최상단에 있는 보석의 무게를 m이라고 할 때, m 이상의 무게를 담을 수 있는 가방들 중 첫 번째 것을 찾는다.
   2. 찾았을 경우, 담은 보석의 가치 총합(result)에 우선순위 큐 최상단에 있는 보석의 가치 v를 더해준다.
   3. 그리고, 사용한 가방은 multiset에서 제거(erase)해준다. -> 시간복잡도 logn
   4. 보석을 가방에 담든, 담지 않든 최상단의 보석은 사용했거나 더 이상 사용하지 않을 것이므로 우선순위 큐에서 제거해준다.

코드 작성

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#define ULL unsigned long long
using namespace std;

priority_queue<pair<int, int>> pq;
multiset<int> ms;

ULL result = 0;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int m, v;
        cin >> m >> v;
        pq.push({v, m});
    }
    for (int i = 0; i < k; i++) {
        int c;
        cin >> c;
        ms.insert(c);
    }

    while (!pq.empty()) {
        int v = pq.top().first;
        int m = pq.top().second;

        auto it = ms.lower_bound(m);
        if (it != ms.end()) {
            result += v;
            ms.erase(it);
        }

        pq.pop();
    }
    cout << result;
    return 0;
}