보석 도둑 1202

문제

접근 방법

보석은 가치가 높은 순으로, 가방은 크기가 작은 순으로 정렬해두고 찾으면 된다고 생각했다.

코드

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    multiset<int> bag;
    vector<pair<int, int>> jewelry;
    int N, K;
    ull sum = 0;
    cin >> N >> K;
    for (int i = 0; i < N; ++i)
    {
        pair<int, int> j;
        cin >> j.second >> j.first;
        jewelry.push_back(j);
    }
    for (int j = 0; j < K; ++j)
    {
        int b;
        cin >> b;
        bag.insert(b);
    }
    sort(jewelry.begin(), jewelry.end(), greater<>());
    for (auto j : jewelry)
    {
        auto it = bag.lower_bound(j.second);
        if (it != bag.end())
        {
            bag.erase(it);
            sum += j.first;
        }
    }
    cout << sum;
}

풀이

처음에는 벡터와 우선순위 큐로 풀려 했다. 가방 벡터를 앞에서부터 확인하며 erase하는 방식으로 풀려 하니 시간초과가 났다. 찾아보니 벡터의 erase는 O(n)이고 set의 erase는 O(logn)이기에 set을 사용해야 하는 것을 알게 됐다.
무게가 중복될 수 있다는 점에서 그냥 set이 아닌 multiset을 사용해야 한다.
또한 sum은 int범위를 초과하기에 범위가 넓은 자료형을 써줘야 한다.
lower_bound로 보석 무게보다 무겁거나 같은 가방을 가져와서 사용해주면 된다.

찾아보니 이러한 방법 말고 가방과 보석을 작은 무게순으로 정렬해두고 작은 가방부터 가져와서 가방 무게보다 작거나 같은 보석들을 우선순위 큐에 넣어 큰 가치를 가지고 있는 보석을 빼는 방식이 있었다. 이것이 더 효율적이고 문제의 의도가 담긴 풀이라고 생각한다.