백준 1202(보석 도둑) c++

문제

1202번: 보석 도둑

n개의 보석의 무게와 가격이 주어지고, k개의 가방의 최대 수용 무게가 주어집니다.

이 때 가방은 최대 1개의 보석만 넣을 수 있다고 가정할 때, 도둑이 훔쳐갈 수 있는 최대 가격을 구하는 문제입니다.

(n <= 300000, k <= 300000)

 

처음에 이 문제를 접했을 때는 knapsack 알고리즘인줄 알았지만, 가방이 최대 1개의 보석만을 넣을 수 있으므로

knapsack은 아닙니다.

결국 가방의 무게보다 작거나 같으면서 그 중 최대의 가격을 가지는 보석을 넣어야 합니다.

최대, 최소를 빠르게 구하는 방법은 "우선순위 큐"를 구하는 것입니다.

먼저 보석의 무게를 기준으로 오름차순으로 정렬해주고, 가방의 최대 무게 또한 오름차순으로 정렬해줍니다.

그 다음 가방이 수용할 수 있는 무게까지 우선순위 큐에 모두 집어넣고, 맨위에 있는 요소를 pop해주면

현재 내가 선택한 가방이 수용할 수 있는 무게중 가장 큰 가격을 갖는 것을 뱉어냅니다.

이를 k번 반복해 주면됩니다. 그렇게 되면 결국 한번 확인한 보석들은 이미 큐에 들어가 있기 때문에 안봐도 됩니다.

ll ans = 0;
   	int idx = 0;
    for (int i = 0; i < k; i++)
    {
        int cur = bag_weight[i];
        while (v[idx].first <= cur && idx < n) 
        {
            pq.push(v[idx].second);
            idx++;
        }
        if (!pq.empty())
        {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
pair<int, int> v[300001];
int bag_weight[300001];
priority_queue<int> pq;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        v[i].first = a;
        v[i].second = b;
    }
    for (int i = 0; i < k; i++)
        cin >> bag_weight[i];
    sort(v, v + n);

    sort(bag_weight, bag_weight + k);

    ll ans = 0;
    int idx = 0;
    for (int i = 0; i < k; i++)
    {
        int cur = bag_weight[i];
        while (v[idx].first <= cur && idx < n)
        {
            pq.push(v[idx].second);
            idx++;
        }
        if (!pq.empty())
        {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;

    return 0;
}