[ 백준 1202 ] 보석 도둑 (C++)

백준의 보석도둑(1202) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

훔칠 수 있는 보석 가격의 최댓값을 구해야 하는 문제이다.

각 가방에는 보석을 딱 한개만 담을 수 있고, 가방마다 담을 수 있는 최대 무게가 다르다.

그렇다면, 보석을 선택할 때, 어떤 보석부터 우선적으로 처리해야 하는지에 대해서부터 생각을 해보자.

보석의 최대가격이니까 가격이 높은 보석부터 처리해주면 될 것이다 라고 생각할 수 있지만, 사실 무게부터 고려를

해봐야 한다.

아무리 가격이 높은 보석이라고 하더라도, 해당 보석의 무게가 가방이 담을 수 있는 최대 무게보다 더 나간다면

보석을 가져갈 수 없기 때문이다.

즉, 무게가 낮은 보석부터 우선적으로 고려를 해주어야 한다. 물론, 무게가 같은 보석이 여러개라면 당연히 가격이 더 높은

보석이 더 우선적으로 선택되어야 할 것이다.

따라서, 본인은 가장먼저 가방을 무게순으로, 보석을 무게순으로(무게가 같으면 가격이 더 높은 순으로) 정렬을 해주었다.

그 이후에는 가방에 순서대로 보석을 집어넣어줄 것인데(가방도, 보석도 모두 정렬되어 있는 상태), 이 과정에서

우선순위큐를 사용해 주었다.

가장 가벼운 보석부터 순서대로 가방의 무게와 비교했을 때, 가방에 들어갈 수 있는 보석들의 가격을 우선순위 큐에 넣어

주었다. 그렇게 되면, 우선순위큐에 가장 top()에는 "현재 가방에 들어갈 수 있는 보석들 중에서 가장 높은 가격을 가진

보석"이 들어있을 것이다. 이 후에 우선순위큐에서 하나씩 빼면서 모든 값을 더해주었다.

[ 소스코드 ]

/* STL Priority_Queue 사용 Ver. */
#include<iostream>
#include<queue>
#include<algorithm>
 
#define endl "\n"
#define MAX 300010
typedef long long ll;
using namespace std;
 
struct DIAMOND
{
    int Weight;
    int Price;
 
    bool operator<(DIAMOND &Cmp)
    {
        if (Weight <= Cmp.Weight)
        {
            if (Weight == Cmp.Weight)
            {
                if (Price > Cmp.Price)
                {
                    return true;
                }
                return false;
            }
            return true;
        }
        return false;
    }
};
 
int N, K;
int Bag[MAX];
ll Answer;
DIAMOND Arr[MAX];
 
void Input()
{
    cin >> N >> K;    
    for (int i = 0; i < N; i++)
    {
        int a, b; cin >> a >> b;
        Arr[i].Weight = a;
        Arr[i].Price = b;
    }
    for (int i = 0; i < K; i++)
    {
        cin >> Bag[i];
    }
}
 
void Solution()
{
    sort(Bag, Bag + K);
    sort(Arr, Arr + N);
    priority_queue<int> PQ;
 
    int Idx = 0;
    for (int i = 0; i < K; i++)
    {
        int Bag_Size = Bag[i];
        
        while (Idx < N)
        {
            int Diamond_Size = Arr[Idx].Weight;
            int Diamond_Price = Arr[Idx].Price;
 
            if (Diamond_Size <= Bag_Size)
            {
                PQ.push(Diamond_Price);
                Idx++;
            }
            else break;
        }
 
        if (PQ.empty() == false)
        {
            Answer = Answer + PQ.top();
            PQ.pop();
        }
    }
    cout << Answer << endl;
}
 
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;
}