[백준][C++] 1202번: 보석 도둑 <214>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1202번: 보석 도둑

생각의 흐름

그리디(Greedy) 알고리즘에 우선순위 큐(Priority Queue) 를 사용하는 문제입니다.

 

1) 우선 입력으로 받은 가방의 무게와 보석의 허용 최대 무게를 기준으로 오름차순으로 정렬해줍니다.

2) 이후 가방의 수만큼 반복문을 돌면서

     i) 해당 가방이 허용할 수 있는 보석까지 우선순위 큐에 우선 넣습니다.

     ii) pritority_queue는 maxHeap이기 때문에 가장 비싼 보석이 root에 있게됩니다.

     iii) 따라서, 우선순위 큐의 root에 있는 보석을 가방에 넣어주고 해당 보석을 우선순위 큐에서 pop합니다.

 

1, 2번을 반복하게 됩니다!

 

나의 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 1000001

int N, K;

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

    cin >> N >> K;
    vector<pair<int, int>> jewelry(N);
    vector<int> bag(K);
    for(int i = 0; i < N; i++) {
        int M, V;
        cin >> M >> V;
        jewelry[i] = {M, V};
    }
    for(int i = 0; i < K; i++) {
        int num;
        cin >> num;
        bag[i] = num;
    }

    // 가방, 보석 오름차순 정렬
    sort(jewelry.begin(), jewelry.end());
    sort(bag.begin(), bag.end());

    priority_queue<int> pq;
    long long res = 0;
    int index = 0;
    for(int i = 0; i < K; i++) {
        while(index < N && jewelry[index].first <= bag[i]){
            pq.push(jewelry[index++].second);
        }
        if(!pq.empty()) {
            res += pq.top();
            pq.pop();
        }
    }
    cout << res << "\n";

    return 0;
}