[백준] [C++] 보석 도둑 1202번

문제 설명

백준 보석 도둑

그리디 알고리즘을 사용해야 한다. 아니면 무조건 시간초과 발생.

접근 방법

작은 가방부터 담아야 한다. -> 가방을 정렬

가방에 담을 때, 가방에 담을 수 있는 것중에 가장 가치가 높은 것부터 담아야 그리디 알고리즘이다.

우선순위 큐를 이용한 풀이

cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define MAX 300001


/*
그리디 알고리즘의 좋은 문제
가방의 용량이 주어졌을 때 담을 수 있는 물품중에 가장 가치가 높은 물품을 담는다.
*/

int N, K;
pii jewerly[MAX];
int C[MAX];
priority_queue<int> pq;

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

    cin >> N >> K;
    for (int i=0; i<N; i++){
        cin >> jewerly[i].first >> jewerly[i].second;
    }
    for (int i=0; i<K; i++){
        cin >> C[i];
    }

    // 무게 순으로 정렬
    sort(jewerly, jewerly+N);
    sort(C, C+K);

    int idx = 0;
    ll sum = 0;

    // 작은 가방부터 최적의 가치를 넣기
    for (int i = 0; i < K; i++) {

        // 넣을 수 있는 것들 pq에 일단 넣기
        while (idx < N) {
            if (C[i] < jewerly[idx].first) break;  // 못담는 무게 나오면
            pq.push(jewerly[idx].second);
            idx++;
        }

        // 넣을 수 있는 것중에 가치가 가장 높은 물건 넣기
        // 나머지는 그대로 저장하는게 중요
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }

    cout << sum;

    return 0;
}

마무리

가방을 작은 순서로 정렬한 후, 넣을 수 있는 보석 중에서 가치가 높은 것부터 넣는다는 생각이 매우 하기 어려웠다.

우선순위 큐를 사용하는 문제들은 참 생각하기 어려운 것 같다.

근데 참 매력적인 문제인것 같다.