[BOJ/C++] 1202: 보석 도둑

🏅 Gold 2

✏️ 1차 솔루션

⭐️ 우선순위 큐 사용

1. 가방은 무게 오름차순 정렬
2. 보석은 가격을 기준으로 내림차순 정렬
3. 가방의 최대무게보다 보석 무게가 작거나 같으면 보석 담을 수 있음 ➡️ 해당 보석 가격 기록해두고 보석 큐와 가방 큐 모두 pop
   아니면 보석 큐만 pop 해서 다음 보석은 담을 수 있는지 이어서 판단

🚨 1차 trouble

틀렸다고 뜬다ㅠㅠ 예외사항 있을 수도?

✏️ 최종 솔루션

1. 가방은 오름차순 정렬
2. 보석은 무게 작은 순서대로 오름차순 정렬
3. 모든 가방에 대해서 가방이 담을 수 있는 보석의 가격은 최대 히프에 넣기 ➡️ 가능한 보석을 모두 담으면 top 에 해당 가방이 가능한 보석 중에 최대 가격이 오게 되므로 top 값만 ans 에 더해주기
   ❗️앞에 있는 가방에 보석을 넣을 수 있어서 이미 넣어줬다면 다음 가방은 수용 무게가 더 큰 가방이므로 남아있는 보석도 넣을 수 있으면서 다음 보석들도 넣을 수 있기 때문에 이전 가방이 넣지 못한 보석부터 이어서 현재 가방에 넣을 수 있는지 확인해야 함

📌 self feedback

원리는 비슷하나 진짜 왜 틀렸는지 모르겠지만 다른 방법으로 접근할 수 있었던 문제라 기록함

✏️ 최종 code

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct value {
    int m;
    int v;
};

bool cmp(value a, value b) {
    return a.m < b.m;
}

int main() {
    int n,k;
    long long ans=0;
    vector<int> bag;
    vector<value> jwerly;
    priority_queue<int> pq;
    cin >> n >> k;

    while(n--) {
        int m,v;
        cin >> m >> v;
        jwerly.push_back({m,v});
    }

    while(k--) {
        int b;
        cin >> b;
        bag.push_back(b);
    }

    sort(bag.begin(), bag.end());
    sort(jwerly.begin(), jwerly.end(), cmp);

    int idx=0;

    for (int i=0; i<bag.size(); i++) {
        while (idx<jwerly.size() && jwerly[idx].m<=bag[i]) {
            pq.push(jwerly[idx++].v);
        }

        if (!pq.empty()) {
            ans+=pq.top();
            pq.pop();
        }

    }

    cout << ans;

}