[백준 1202] 보석 도둑

🔗 알고리즘 문제

시간초과를 해결하기 위해 애를 쓴 그리디 문제이다.

문제 분석

이 문제는 도둑이 가져갈 수 있는 최대 가격의 보석을 알아내는 간단한 그리디 문제이다.

발상 & 알고리즘 설계

간단한 그리디 발상으로 접근할 수 있는 문제이지만, 들어오는 데이터들이 많기 때문에 조금 생각을 해줘야 한다.

입력받은 보석들과 가방의 담을 수 있는 크기를 각각 배열로 담아 오름차순으로 정렬하여 주고 for문을 돌며 가방에 담을 수 있는 것들을 모두 우선순위 큐에 담아주었다.

현재 가방에 담을 수 있는 모든 것을 우선순위에 담았다면, 가방에 넣을 수 있는 가장 비싼 보석은 우선순위 큐에 맨 위에 있을 것이기에 ans에 값을 담아주었다.

코드

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

using namespace std;

int main(){
    int n;
    int k;

    long long ans = 0;

    pair<long long, long long> zems[300001];
    long long bags[300001];

    cin >> n >> k;

    for(int i = 0; i < n; i++){
        long long weight;
        long long price;

        cin >> weight >> price;

        zems[i] = { weight, price };
    }

    for(int i = 0; i < k; i++){
        cin >> bags[i];
    }

    sort(bags, bags + k);
    sort(zems, zems + n);

    priority_queue<long long> pq;
    int idx = 0;

    for(int i = 0; i < k; i++){
        long long bag = bags[i];

        while(idx < n && zems[idx].first <= bag){
            pq.push(zems[idx].second);
            ++idx;
        }

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

    cout << ans;
}