(2024-11-03) 2 문제 : 백준 - 1202 (보석 도둑)

 

이 문제는 우선순위큐와 lower_bound를 활용해서 해결하였다.

 

먼저, 보석을 모두 우선순위 큐에 넣어준다. 이 때, 우선순위 기준을 직접 만들어야 하는데 가치는 제일 높은 것이 top으로 오게 해야하고 만약 가치가 같다면 더 낮은 무게가 top으로 오도록 해야한다. 

 

또한, 가방의 무게를 담을 자료구조가 필요한데 본인은 multiset을 사용하였다. lower_bound를 사용할 때 벡터를 사용하면 매번 원소를 삭제하거나 정렬해야 하기 때문에 시간 복잡도가 높아지고 list를 사용했더니 또 시간초과가 발생하였다.

 

그래서 multiset의 lower_bound 멤버함수를 사용했는데, 이게 std::lower_bound를 사용할 땐 시간초과가 발생했고 멤버함수를 사용했을 땐 시간초과가 안났다. 두 함수의 차이에 대해 좀 알아봐야 할 듯 하다.

 

아무튼 이후, 우선순위큐가 빌때까지 반복문을 돌려준다. 현재 우선순위큐의 top에 있는 보석 무게를 기준으로 가방이 담긴 자료구조에서 해당 보석을 담을 수 있는 가방중 가장 최대무게가 낮은 가방을 골랐다. 선택된 가방은 자료구조에서 제거하였고 보석의 가치는 정답에 누적해주었다. 이 과정을 우선순위 큐가 빌때까지 반복하지만, 중간에 만약 가방의 개수가 0이 된다면 그 때는 반복문을 탈출하도록 해주었다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
#include <set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

struct Compare
{
    bool operator()(const std::pair<int, int>& _Left, const std::pair<int, int>& _Right)
    {
        if (_Left.first == _Right.first)
        {
            return _Left.second > _Right.second;
        }

        return _Left.first < _Right.first;
    }
};

int main()
{
    Init();

    int NumJewerly = 0;
    int NumBag = 0;
    std::cin >> NumJewerly >> NumBag;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Compare> Jewerlies;

    for (int i = 0; i < NumJewerly; i++)
    {
        int Weight = 0, Value = 0;
        std::cin >> Weight >> Value;

        Jewerlies.push({Value, Weight});
    }

    std::multiset<int> Bags;
    for (int i = 0; i < NumBag; i++)
    {
        int BagWeight = 0;
        std::cin >> BagWeight;

        Bags.insert(BagWeight);
    }

    long long Answer = 0;
    
    while (Jewerlies.size() > 0)
    {
        auto [CurValue, CurWeight] = Jewerlies.top();
        Jewerlies.pop();
        
        auto FindIter = Bags.lower_bound(CurWeight);

        if (FindIter != Bags.end())
        {
            Answer += CurValue;
            Bags.erase(FindIter);
        }

        if (Bags.size() ==  0)
        {
            break;
        }
    }

    std::cout << Answer;

    return 0;
}