[백준(BOJ)] 보석 도둑(1202번)_C++

무게가 적으면서 가격이 높은 보석들만 존재할 수도 있기 때문에 무게가 적은 보석과 가방부터 검사하는 것이 용이하다.

그래서 나는 보석과 가방을 무게의 오름차순으로 정렬했다.

 

모든 가방에 대해 가능한 보석들 중 가장 가격이 높은 보석을 골라야 한다.

이를 그냥 2중for문으로 구현하면 당연히 O(nk)로 시간초과가 발생한다.

때문에 처음에 나는 이분탐색을 활용해서 가방에 넣을 보석을 찾으려 했는데 기준이 되는 값이 무게와 가격, 2가지라서 이분탐색으로 진행하기 어려웠다.

 

조금만 잘 생각해보면 보석과 가방 모두 무게 순으로 정렬했기 때문에 i-1번째 가방에 들어갈 수 있는 후보 보석들은 i번째 가방에서도 후보가 된다. 이를 이용하면 매번 가방을 검사할 때마다 모든 보석을 검사할 필요없이 이전에 후보가 아니었던 보석부터 검사하면 된다. 즉, 가방을 검사하면서 후보 보석들을 늘려나가면 된다.

 

그런데 후보 보석들 중 가격이 가장 높은 보석을 찾는 것도 시간이 걸렸다. 그래서 저장할 때 O(logn)으로 정렬되면서 저장되는 maxheap을 떠올렸다.

maxheap 구조인 우선순위큐를 사용하면 O(klogn)만에 가격의 최댓값을 구할 수 있다.

 

주의할 점은 가격의 최댓값이 int 형의 범위를 넘으므로 long long 형으로 구해야 한다.

 

---

정답

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

using namespace std;

int n, k;
vector<pair<int, int>> jewel;
vector<int> c;
priority_queue<int> candidate;
long long answer;

bool cmp(pair<int, int> a, pair<int, int> b){
    if (a.first < b.first)
        return true;
    else if (a.first > b.first)
        return false;
    else if (a.first == b.first){
        if (a.second < b.second)
            return true;
        else
            return false;
    }
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int m, v;
        cin >> m >> v;
        jewel.push_back({m, v});
    }
    for(int i = 0; i < k; i++){
        int a;
        cin >> a;
        c.push_back(a);
    }

    //sort
    sort(c.begin(), c.end());
    sort(jewel.begin(), jewel.end(), cmp);

    //solve
    int idx = 0; //후보 보석 개수
    for(int i = 0; i < k; i++){
        while (idx < n && c[i] >= jewel[idx].first)
            candidate.push(jewel[idx++].second);
        
        if (!candidate.empty()){
            answer += candidate.top();
            candidate.pop();
        }
    }

    //output
    cout << answer;
}