[백준] 보석 도둑

그리디 유형의 백준 문제를 또 한번 풀어봤다. 가방 K 개가 있고 보석 N 개가 각각 무게와 값어치로 주어질때 가방 K개로 만들 수 있는 최대치의 값을 반환하면 된다. 이때, 가방은 하나만 존재하고 담을 수 있는 무게의 제한이 각 가방마다 있다.

언뜻보면은 DP 문제일까 하고 쫄아서 안풀수도 있지만 우선순위큐를 사용한 그리디 문제라고 하기에 바로 아이디어를 적용해봤다.

일단 가장 많이 담을 수 있는 가방을 오름차순으로 정렬해주고 보석또한 무게가 낮은 순서로 오름차순을 해주었다. 여기서 좀 내가 캐치를 못했던거는 이중 루프를 이용해서 하나의 가방 마다 담을 수 있는 무게를 우선순위 큐에 넣는것이었다.

만약 담을 수 있는 가방까지 우선순위 큐에 넣게되면 당연히 가장 앞에 있는 무게가 값어치 또한 높기때문에 답에 더해주면 된다. 우선순위큐에는 무게 순서가 아닌 값어치 순서대로 넣어준다면 가장 값어치가 높은 무게부터 첫번째 순서에 배치될것이다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, K; 
priority_queue<pair<int,int>,vector<pair<int,int>>> pq; 
vector<pair<int,int>> jewels; 
vector<int> bags; 

void Input(){
    cin >> N >> K; 
    for(int i = 0; i < N; i++){
        int a, b; 
        cin >> a >> b; 
        jewels.push_back({a,b}); 
    }
    for(int i = 0; i < K; i++){
        int a;
        cin >> a;
        bags.push_back(a); 
    }
}

void Solution(){
    sort(bags.begin(),bags.end()); 
    sort(jewels.begin(),jewels.end()); 
    long long answer = 0; 
    int cnt = 0; 
    for(int i = 0; i < bags.size(); i++){
        
        for(int j = cnt; j < jewels.size(); j++){
            if(jewels[j].first > bags[i]) break; 
            pq.push({jewels[j].second,jewels[j].first}); 
            cnt++; 
        }

        if(!pq.empty()){
            answer += (long long)pq.top().first;
            pq.pop(); 
        }
    }
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. 2중 루프를 무서워 하지말자
2. 아이디어의 중요성