[BOJ/C++] 1202번: 보석도둑

 

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

1202번: 보석 도둑

우선순위큐와 그리디 알고리즘을 적절히 섞어 써서 시간제한 내에 연산하는 것이 포인트였습니다.

1. 각 보석의 무게와 가치를 튜플 배열로 입력 받습니다.
2. 각 가방 용량의 최대치를 입력 받습니다
3. 각 보석은 무게순으로, 각 가방은 용량 순으로 오름차순 정렬합니다.
4. 각 가방의 용량을 순회하면서 가방에 담을 수 있는 보석들의 가치를 우선순위큐(maxheap)에 담습니다.
5. 이 경우 우선순위큐의 top은 현재 가방의 용량보다 무게가 적으면서 가장 가치가 높은 보석입니다. 이를 최종 결과값 result에 더해줍니다.
6. 4번~5번과정을 우선순위큐가 비어있지 않는 동안 반복합니다. 

추가로 정답을 저장할 result 변수는 경우에 따라 int의 최대값을 넘길 수 있음으로 long long 으로 선언해야합니다.

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

using namespace std;

int N, K;
vector<int> bag;
vector<pair<int, int>> jewelry;
priority_queue<int> pq;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    bag.resize(K); 
    jewelry.resize(N);
    for (int i = 0; i < N; i++) cin >> jewelry[i].first >> jewelry[i].second;
    for (int i = 0; i < K; i++) cin >> bag[i];
    sort(jewelry.begin(), jewelry.end());
    sort(bag.begin(), bag.end());

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