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

1202번: 보석 도둑

그리디와 우선 순위 큐를 이용하는 문제이다. 각 배낭마다 최대 무게가 있고 최대 한개의 보석만을 담을 수 있다. 우선 입력받은 보석 정보들과 가방 무게들을 오름차순으로 정렬해주었다. 그 후 반복문을 돌며 해당 배낭의 무게에 담을 수 있는 보석들의 가격을 우선 순위 큐에 넣고 이들 중 가장 비싼 가격을 합에 더해주고 pop해주었다. 이를 반복하여 각 배낭들이 가질 수 있는 최대 가격을 알 수 있고 이를 더한 값을 출력해주었다. 아이디어가 쉽게 떠오르지 않은 문제였다. 처음에는 모든 보석들을 처음부터 우선 순위 큐에 넣어 무게 순서대로 정렬해 가격의 합을 구했는데 이렇게 할 경우 최대값이 나오지 않았었다. 이러한 방식도 있다는 것을 알아두어야 겠다.

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

using namespace std;

int N, K;
vector<pair<int, int>> v;
vector<int> c;

void solution() {
    priority_queue<int> pq;

    sort(c.begin(), c.end());
    sort(v.begin(), v.end());

    long long sum = 0;
    int idx = 0;
    for (int i = 0; i < K; i++) {
        int weight = c[i];

        for (int j = idx; j < N; j++) {
            int M = v[j].first;
            int V = v[j].second;

            if (M <= weight) {
                pq.push(V);
                idx++;
            }
            else {
                break;
            }
        }

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

    cout << sum;
}

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

    cin >> N >> K;

    int M, V;
    for (int i = 0; i < N; i++) {
        cin >> M >> V;
        v.push_back({ M, V });
    }

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

    solution();

    return 0;
}