백준 1202번 보석 도둑 - 우선순위큐 활용 C++

1. 문제설명

보석에는 무게와 가격이 존재하고,

각 가방마다 챙길 수 있는 최대 무게가 존재합니다.

그리고 각 가방에는 최대 하나의 보석만 넣을 수 있습니다.

 

이러한 조건이 있을 때 도둑이 여러 개의 가방을 통해 챙길 수 있는 보석들의 가격의 최대 합을 구해야합니다.

 

우선 각 가방마다 챙길 수 있는 보석의 최대 무게가 다른 조건을 생각해보면,

가방의 최대 무게가 크면 여러개의 보석을 선택할 수 있고,

가방의 최대 무게가 작으면 선택할 수 있는 보석이 줄어듭니다.

 

이를 바탕으로 최대 무게가 작은 가방부터 보석을 선택해나가면 됩니다.

그리고 각 가방이 챙길 수 있는 최대 무게의 보석을 챙겨야 합니다.

 

이를 위해서 현재 가방의 최대 무게를 바탕으로

현재 가방에 담을 수 있는 보석을 우선순위 큐에 넣고,

더이상 담을 수 있는 보석이 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 선택하는 방식으로 문제를 해결할 수 있습니다.

 

 

정리하면

배낭을 최대 무게를 바탕으로 오름차순으로 정렬하고,

보석을 무게를 바탕으로 오름차순으로 정렬해서

 

배낭의 무게를 작은 값부터 돌면서

무게가 작은 보석부터 넣을 수 있는 보석을 우선순위 큐에 넣고,

더이상 넣을 수 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 답에 더해주는 것을 반복하면 됩니다.

 

이렇게 하면

항상 가방은 해당 가방이 선택할 수 있는 보석의 최대 가격을 선택하게 됩니다.

 

 

---

 

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int n, k;

struct Jew{
    int m, v;
    bool operator<(const Jew& a) const {
        return v < a.v;
    }
};

vector<pair<int,int> > jew;
vector<int> backpack;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    long long ans = 0;

    for(int i=0; i<n; i++){
        int m, v;
        cin >> m >> v;

        jew.push_back({m,v});
    }

    for(int i=0; i<k; i++){
        int c;
        cin >> c;
        backpack.push_back(c);
    }

    sort(jew.begin(), jew.end());
    sort(backpack.begin(), backpack.end());

    int ptr = 0;

    priority_queue<Jew> pq;

    for(int i=0; i<k; i++){

        while(ptr<n && jew[ptr].first <= backpack[i]){
            pq.push({jew[ptr].first, jew[ptr].second});
            ptr++;
        }

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

    }


    cout << ans << '\n';
    return 0;
}