보석 도둑

백준 1202

GOLD II

1. 문제 내용
2. 해결 방안
3. 풀이 코드

---

문제 내용

문제 링크

해결 방안

문제를 정리하자면, 최대 무게가 정해진 K개의 가방에 무게와 가격이 주어진 보석들의 가격의 합이 최대가 되도록 보석을 담는 방식을 찾아야 한다. 언뜻 보기에는 배낭 문제처럼 보이지만, 가방에 보석을 최대 1개까지만 넣을 수 있고, 가방과 보석의 정보가 최대 300,000개나 주어지기 때문에 배낭 문제 풀이는 적합하지 않다. 대신 각 가방별로 최대 가격의 보석을 넣는 그리디 알고리즘을 사용하여 간단히 풀 수 있다.

우선 보석과 가방을 각각 무게와 최대 적재량에 대해 오름차순으로 정렬하고, 각 가방에 대해 담을 수 있는 보석들을 가격이 높은 보석이 앞으로 가는 우선순위 큐에 모두 넣는다. 그 후, 큐에 보석이 있다면 가장 가격이 높은 보석을 내보내, 그 가격을 더한다. 배낭이 담을 수 있는 무게에 대해 오름차순으로 정렬되어 있으므로, 다음 배낭은 현재 배낭에 들어갈 수 있는 보석을 무조건 담을 수 있다. 때문에 다음 배낭은 이전 배낭에 이어 현재 담을 수 있는 보석만 추가로 우선순위 큐에 넣어주면 된다. 결과적으로, 모든 가방에 대해 넣을 수 있는 보석을 꺼내고, 꺼내진 보석들의 가격의 합이 문제에서 요구하는 보석의 합의 최댓값이 된다.

우선순위 큐(priority queue)란?

본래의 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 그러나, 우선순위 큐(priority queue)는 이름 그대로 먼저 나가는 우선순위가 있는 큐의 성질을 띠는데, 이 때문에 우선순위 큐는 데이터 삽입 및 삭제 시 내부 요소들을 정렬하는 데에 용이한 힙(heap) 자료구조를 통해 구현된다.

풀이 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<long, long> jewel;

jewel jewels[300000];
long bag[300000];
priority_queue<int, vector<int>, less<int>> price;

int n, k;
long price_sum = 0;
int jewel_index = 0;

int main() {
    // Fast IO in C++
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    // 보석 및 가방의 정보 입력
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> jewels[i].first >> jewels[i].second;
    for(int i = 0; i < k; i++)
        cin >> bag[i];
    
    // 보석과 가방을 각각 무게와 최대 적재량을 기준으로 오름차순 정렬
    sort(jewels, jewels + n);
    sort(bag, bag + k);
    
    // 각 가방에 대해 다음과 같은 명령 실행
    for(int i = 0; i < k; i++) {
        // 현재 배낭에 담을 수 있는 보석의 가격들을 모두 추가
        while(jewel_index < n && jewels[jewel_index].first <= bag[i])
            price.push(jewels[jewel_index++].second);
        
        // 우선순위 큐에서 가장 높은 가격을 꺼내어 합산
        if(!price.empty()) {
            price_sum += price.top();
            price.pop();
        }
    }
    
    cout << price_sum << endl;
    return 0;
}

---