[백준 1202] 보석 도둑(C++ 풀이)

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

---

풀이

이 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다.

 

우선 보석의 정보와 가방의 정보를 담을 배열 그리고 우선순위 큐를 다음과 같이 정의한다.

pair<int, int> v_jewerly[MAX];
int v_bag[MAX];
priority_queue<int> pq;

원래는 vector 자료형을 사용했었는데, 배열 최대크기(MAX = 300001)가 너무 커서 메모리 초과가 나왔다. 따라서 일반 배열로 선언해준다.

 

그 후 배열에 입력을 받고, 보석 정보와 가방의 정보를 모두 오름차순으로 정렬한다.

sort(v_jewerly, v_jewerly+N);
sort(v_bag, v_bag+K);

 

그 후 가방의 무게가 낮은 가방부터 탐색하면서, 해당 가방에 넣을 수 있는 보석을 모두 pq에 push한다.

pq에 보석을 넣고 나면, pq의 top에 있는 보석(넣을 수 있는 보석 중 가장 비싼 보석)을 꺼내서 sum에 더해준다.

 

    for (int i = 0; i < K; i++) {
        while (idx < N && v_bag[i] >= v_jewerly[idx].first) {
            pq.push(v_jewerly[idx].second);
            idx++;
        }
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }

 

 

 

전체 소스 코드

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

#define MAX 300001
using namespace std;

int N; // 보석 수
int K; // 가방수


pair<int, int> v_jewerly[MAX];
int v_bag[MAX];
priority_queue<int, vector<int>, less<int>> pq;


long long solve() {
    sort(v_jewerly, v_jewerly+N);
    sort(v_bag, v_bag+K);

    int idx = 0;
    long long sum = 0;

    for (int i = 0; i < K; i++) {
        while (idx < N && v_bag[i] >= v_jewerly[idx].first) {
            pq.push(v_jewerly[idx].second);
            idx++;
        }
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }
    return sum;
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        cin >> v_jewerly[i].first >> v_jewerly[i].second;
    }
    for (int i = 0; i < K; ++i) {
        cin >> v_bag[i];
    }
    cout << solve();
}