[백준 1202] 보석 도둑

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

으아아 아직 그리디 문제에 대한 감이 부족한 것 같다. 그리디 문제를 좀 많이 풀어봐야겠다.

보석의 무게와 배냥의 무게를 정렬해야겠다는 생각까지는 하였으나, 가치를 어떻게 정렬 해야할지 고민을 제대로 하지 않고 처음엔 보석과 배낭의 크기를 정렬하고 하나씩 증가하며 비교를 하려고 했는데, 양이 무지하게 많아 시간초과가 되었고, 풀이를 보니 기존 계산한 값을 우선순위 큐에 저장하는 그리디 문제였다.

시간 복잡도로 생각해보면, 우선순위 큐를 사용하지 않을 경우 n번의 보석을 k번 비교하므로 O(NK)이고, 우선순위 큐를 사용할 경우, O(logN)을 N (idx<n) 번 반복하므로 O(NlogN)이 된다.

풀이과정

1. 보석과 가방을 오름차순으로 정렬한다.
2. 가방의 용량이 작은 것 부터, 들어갈 수 있는 모든 보석들을 우선순위 큐에 저장한다.
   • 용량이 큰 가방은 작은 가방이 넣을 수 있는 보석을 모두 넣을 수 있기 때문이다.
3. 우선순위 큐에서 보석 하나를 빼 작은 가방에 넣는다.

예)
보석의 무게가 {1} {2} {3} {4} 라면, 무게가 2인 가방은 {1},{2}를 큐에 넣고 이들 중 가치가 큰 보석을 하나 빼온다. 그 후 무게가 4인 가방은 이미 있는 큐에 {3} {4}의 무게를 가진 보석을 넣고 그들 중 가장 가치가 큰 보석을 꺼낸다.

구현

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<pair<int, int>> jewel(n);
    vector<int> bag(k);
    
    for (int i = 0; i < n; i++) {
        cin >> jewel[i].first >> jewel[i].second;
    }
    
    for (int i = 0; i < k; i++) {
        cin >> bag[i];
    }
    
    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    priority_queue<int> pq;
    long long sum = 0;
    int idx = 0;
    
    for (int i = 0; i < k; i++) {
        while (idx < n && jewel[idx].first <= bag[i]) {
            pq.push(jewel[idx++].second);
        }
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }
    
    cout << sum;
    
    return 0;
}