[백준 1202] 보석도둑

시간초과가 떠서 꽤 오래걸렸다.

초기에는 가방에 중심을 두고 작은 순서대로 하나씩 봐가면서 가능한 보석중 가장 가치가 큰 보석을 넣는 방법을 생각했다.

어처피 뒤에오는 더 큰 가방에서는 앞에 온 작은 가방에 넣을 보석을 넣을 수 있기 때문에 작은 가방은 자신의 입장에서 최적의 보석을 고르면 된다.

근데 가장 가치가 큰 보석을 찾는 방법을 for문으로 N번 돌렸더니 시간 복잡도가 총 O(NK)가 되어 시간초과가 떴다.

따라서 힙구조 우선순위 큐를 사용해서 가장 가치가 큰 보석 찾는 시간을 단축했다. 가방의 크기가 커져서 넣을 수 있는 보석이 더 많아지면 그 보석들을 우선순위 큐에 넣어준다. 그리고 매 가방마다 가장 위의 요소를 pop해서 ans에 더하면 된다.

참고로 우선순위 큐에 들어있는 보석들은 i번째 가방에서 모두 선택 가능하다는 것을 알 수 있기 때문에 굳이 무게도 넣을 필요 없이 가치만 넣어서 정렬해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define n_ 300000 + 5
using namespace std;
 
int n, k;
vector<pair<int, int>> jam;
priority_queue<int> sol;
int bag[n_];
bool chk[n_];
 
int main(void) {
    cin >> n >> k;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        jam.push_back({ a,b });
    }
 
    for (int i = 0; i < k; i++) {
        cin >> bag[i];
    }
 
    sort(jam.begin(), jam.end());
    sort(bag, bag + k);
 
    long long ans = 0;
    int j = 0;
    for(int i = 0; i < k; i++) {    //i번째 가방
        while (j < n&&jam[j].first <= bag[i]) {
            sol.push(jam[j].second);
            j++;
        }
        if (!sol.empty()) {
            ans += sol.top();
            sol.pop();
        }
    }
    cout << ans << endl;
}