[백준][C++] 1202: 보석 도둑

문제

1202번: 보석 도둑

풀이

그리디, 자료 구조, 우선순위 큐

 

2가지 방법으로 문제를 풀 수 있다.

 

1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법

보석과 가방을 오름차순으로 정렬한다. 용량이 적은 가방부터 현재 가방에 들어갈 수 있는 보석을 모두 우선순위 큐에 넣는다. 

그렇게 되면, 우선순위 큐의 top에는 현재 가방에 들어갈 수 있으면서 가격이 최대인 보석이 위치하게 된다. 이 보석을 현재 가방에 넣는다. 

이를 가방의 수 K번 반복하면 답을 구할 수 있다. 여기서 보석은 중복으로 우선순위 큐에 들어가면 안 되고, 어차피 이전에 우선순위 큐에 들어가 있는 보석은 현재 가방보다 더 작은 용량의 가방에 넣을 수 있는 보석이 들어있기 때문에, 보석에 대한 검사는 각 보석당 한 번만 이루어지면 된다.

// 보석과 가방 모두 오름차순으로 정렬
    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    long long answer = 0;
    int index = 0;
    for (int i = 0; i < K; ++i)
    {
        // i번 가방에 들어갈 수 있는 보석을 모두 pq에 넣는다.
        // index로 무게가 작은 보석부터 검사하며, index번 보석이 들어갈 수 없을 때까지 pq에 넣는다.
        while (index < N && bag[i] >= jewel[index].first)
        {
            pq.push(jewel[index].second);
            index++;
        }

        // pq의 top에는 i번 가방에 들어갈 수 있으면서 가격이 최대인 보석이다.
        if (false == pq.empty())
        {
            answer += pq.top();
            pq.pop();
        }
    }

 

2. 비싼 보석부터, 자신이 들어갈 수 있는 최소 크기의 가방을 찾는 방법

이번엔 역으로 보석을 기준으로 생각한다. 가장 비싼 보석이 top에 위치하도록 우선순위 큐에 넣는다. 가방은 용량이 중복될 수 있으므로, multiset에 넣는다.

for (int i = 0; i < N; ++i)
{
    int M, V;
    cin >> M >> V;
    jewel.push(make_pair(V, M));
}

 

위에서 말했듯이, 가장 비싼 보석이 우선순위 큐의 top에 위치하게 된다. 그 보석이 들어갈 수 있으면서 용량이 가장 작은 가방을 찾는다. 

for (int i = 0; i < N; ++i)
{
    int V = jewel.top().first;
    int M = jewel.top().second;
    jewel.pop();
    
    auto it = bag.lower_bound(M);
    if (it != bag.end())
    {
        answer += V;
        bag.erase(it);
    }
}

set의 lower_bound 함수는 전달 받은 값이 set의 key에 존재한다면 해당 iterator를 반환한다. set에 존재하지 않는다면, 전달 받은 값보다 큰 key 중에서 가장 작은 key의 iterator를 반환한다. 이렇게 찾은 가방을 multiset에서 제거한다. 만약 lower_bound로 가방을 찾지 못했다면, 해당 보석은 넣을 수 없는 보석이므로 넘어간다. 

 

코드

1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> jewel;
vector<int> bag;
priority_queue<int> pq;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        int M, V;
        cin >> M >> V;
        jewel.push_back(make_pair(M, V));
    }
    for (int i = 0; i < K; ++i)
    {
        int C;
        cin >> C;
        bag.push_back(C);
    }

    // 보석과 가방 모두 오름차순으로 정렬
    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    long long answer = 0;
    int index = 0;
    for (int i = 0; i < K; ++i)
    {
        // i번 가방에 들어갈 수 있는 보석을 모두 pq에 넣는다.
        // index로 무게가 작은 보석부터 검사하며, index번 보석이 들어갈 수 없을 때까지 pq에 넣는다.
        while (index < N && bag[i] >= jewel[index].first)
        {
            pq.push(jewel[index].second);
            index++;
        }

        // pq의 top에는 i번 가방에 들어갈 수 있으면서 가격이 최대인 보석이다.
        if (false == pq.empty())
        {
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;

    return 0;
}

 

2. 비싼 보석부터, 자신이 들어갈 수 있는 최소 크기의 가방을 찾는 방법

#include <iostream>
#include <queue>
#include <set>

using namespace std;

priority_queue<pair<int, int>> jewel;
multiset<int> bag;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        int M, V;
        cin >> M >> V;
        // 가장 비싼 보석이 top에 위치하도록
        jewel.push(make_pair(V, M));
    }
    for (int i = 0; i < K; ++i)
    {
        int C;
        cin >> C;
        bag.insert(C);
    }

    long long answer = 0;
    for (int i = 0; i < N; ++i)
    {
        int V = jewel.top().first;
        int M = jewel.top().second;
        jewel.pop();

        // 보석을 넣을 수 있는 최소 크기의 가방을 찾는다.
        auto it = bag.lower_bound(M);
        if (it != bag.end())
        {
            // 넣을 수 있는 가방이 있다면 추가하고 가방을 삭제한다.
            answer += V;
            bag.erase(it);
        }
    }

    cout << answer;

    return 0;
}