[C++] Boj 1202 보석 도둑

🔵 문제 링크

https://www.acmicpc.net/problem/1202

 

🔵 문제 설명

논리적인 식을 세우는 문제는 아닌 것 같고 최적의 해가 나올 것 같은 상황을 가정해서 그리디하게 풀어야 한다.

내가 생각했을 때 최적의 해가 나올 것 같은 상황은 다음과 같다.

 

최대한 제일 비싼 보석들을 훔쳐야 한다.

근데 보석마다 무게가 정해져 있는데, 이 보석을 가방에 넣을 때, 최대한 보석의 무게와 같아야 한다.

비싸고 가벼운 보석을 무게 용량이 큰 가방에 넣어버렸다고 가정하자.

다른 마땅한 보석이 나오면 그 보석의 무게에 맞는 가방이 없을 수도 있기 때문이다. (가방에는 보석 하나만 넣을 수 있기 때문.)

 

🔵 시도 1 이중 포문

이런 가정을 코드로 구현하여 무식하게 이중 포문을 돌려 보았다. (안 된다는 것을 알면서도...)

하지만 시간 초과가 나왔다.

당연하다.

입력이 최대 30만인데, 이중 포문을 돌면 제한 시간인 1초를 훌쩍 넘어버리기 때문이다. 

 

🔵 시도 2 lower_bound와 multiset을 이용

multiset과 lower_bound라는 것을 알게 되었다.

이 풀이는 보석을 기준으로 담을 수 있는 가장 작은 가방을 찾는 풀이이다.

 

🔷 multiset

• 중복을 허용하는 정렬된 컨테이너이다.
• 내부적으로 red-black tree로 구현되어 있어 항상 정렬된 상태를 유지한다.
• 삽입/삭제 시간은 O(log N)만큼 걸린다.

🔷 lower_bound

• 정렬된 컨테이너에서 사용 가능하다.
• lower_bound(x)는 x 이상인 첫 번째 원소의 iterator를 반환한다.
• 해당하는 원소가 없다면 end()를 반환한다.
• 시간 복잡도는 O(log K)가 걸린다.

 

🔷 코드

#include <iostream>
#include <algorithm> // sort
#include <vector> // stl 정렬 쓰려고
#include <set> // multiset

using namespace std;

int N, K;
vector<pair<int, int>> gem; // 무게, 가격
multiset<int> bag;
long long ans;

int main()
{
    // 보석 개수, 가방 개수
    cin >> N >> K;

    // 보석 info
    for (int i = 0; i < N; i++)
    {
        int m, v;
        cin >> m >> v;
        gem.push_back({ m, v });
    }

    // 가방 info
    for (int i = 0; i < K; i++)
    {
        int c;
        cin >> c;
        bag.insert(c); // 자동 정렬됨
    }

    // 보석 가격 내림차순 정렬
    sort(gem.begin(), gem.end(), [](auto& a, auto& b)
    {
        if (a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    });

    // 가장 비싼 보석을 넣을 수 있는 최대한 딱 맞는 가방 찾기
    for (int i = 0; i < N; i++)
    {
        int m = gem[i].first;
        int v = gem[i].second;

        // 이 보석을 담을 수 있는 가장 작은 가방 찾기
        auto it = bag.lower_bound(m);
        if (it != bag.end())
        {
            ans += v;
            bag.erase(it); // 사용한 가방 제거
        }
    }

    cout << ans;

    return 0;
}

 

🔵 시도 3 우선순위 큐 사용

보석과 가방을 무게 기준 정렬한다.

그리고 가방을 순회하며 해당 가방에 담을 수 있는 모든 보석을 우선순위 큐에 넣고 가장 비싼 보석을 담는다.

이게 더 깔끔한 구현 같다!

 

🔷코드

#include <iostream>
#include <algorithm> // sort
#include <vector> // stl 정렬 쓰려고 원시 배열 대신 vector
#include <queue> // 우선 순위 큐

using namespace std;

int N, K;
vector<pair<int, int>> gem; // 무게, 가격
vector<int> bag;

long long ans;

int main()
{
    // 보석 개수, 가방 개수
    cin >> N >> K;

    // 보석 info
    for (int i = 0; i < N; i++)
    {
        int m, v;
        cin >> m >> v;
        gem.push_back({ m, v });
    }

    // 가방 info
    for (int i = 0; i < K; i++)
    {
        int c;
        cin >> c;
        bag.push_back(c);
    }

    // 보석 무게 오름차순 정렬
    sort(gem.begin(), gem.end());

    // 가방 무게 오름차순 정렬
    sort(bag.begin(), bag.end());

    priority_queue<int> pq; // 가격 기준 max heap
    int gem_i = 0; // 보석 인덱스

    // 가방을 기준으로 어떤 보석을 담을지
    for (int bag_i = 0; bag_i < K; bag_i++)
    {
        int bagWeight = bag[bag_i];

        // 현재 가방에 담을 수 있는 보석들을 모두 pq에 넣음
        // 자동 정렬 됨
        while (gem_i < N && gem[gem_i].first <= bagWeight) 
        {
            pq.push(gem[gem_i].second); // 가격만 넣음
            gem_i++;
        }

        // 가장 비싼 보석을 선택
        // 나머지 보석들은 아직 우선순위 큐에 저장되어 있다.
    	// 다음 가방에선 모두 포함하여 비교.
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }

    std::cout << ans;

    return 0;
}