백준 1202번 보석 도둑

🔒[문제 url]

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

🔑알고리즘

한 가방이 담을 수 있는 보석 중, 가장 가격이 높은 보석을 담는 것이 가장 효율적이다. Greedy

1. $C_i$를 오름차순으로 정렬한다.
2. 보석을 $M_i$ 기준으로 오름차순 정렬한다.
3. 가방을 순회하며, 담을 수 있는 모든 보석의 가격을 priority_queue에 넣는다.
이때, priority_queue는 내림차순으로 정렬한다.
4. 가장 가격이 높은 보석을 담기위해 priority_queue의 top을 담은 뒤 pop 해준다.
5. 모든 가방이 보석을 담거나, 더이상 담을 보석이 없을 때까지 3 4를 반복한다.

🐾부분 코드

typedef pair<int,int> pii;
int n,k,m,v,c;
vector<int> bag;
priority_queue<pii, vector<pii>, greater<pii>> jewel;
priority_queue<int> containLimit; // Sort descending

long long ans = 0;

<전역 변수 선언>
bag : $C_i$를 오름차순 정렬할 vector
jewel : 보석의 $M_i$와 $S_i$를 담고, $M_i$를 기준으로 오름차순 정렬할 queue
containLimit : bag의 원소. 즉 무게가 $C_i$ 이하인 모든 보석을 담을 queue

int bagSize = bag.size();
for(int i = 0; i < bagSize; i++)
{
    // Push all jewels those bag can contain
    for(int j = 0; j < jewel.size(); j++)
    {
        if (jewel.top().first <= bag[i])
        {
            containLimit.push(jewel.top().second);
            jewel.pop();
        }
        // No more jewels to contain
        else break;
    }

    // Contain most valuable jewel
    if(!containLimit.empty())
    {
        ans += containLimit.top();
        containLimit.pop();
    }
}

<3 4 반복 부분>
위에서 설명한 알고리즘대로 보석 담기를 반복한다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
int n,k,m,v,c;
vector<int> bag;
priority_queue<pii, vector<pii>, greater<pii>> jewel;
priority_queue<int> containLimit; // Sort descending

long long ans = 0;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> m >> v;
        jewel.push({m,v});
    }
    for(int i = 0; i < k; i++)
    {
        cin >> c;
        bag.push_back(c);
    }
}


void SOLVE()
{
    // Sort bag ascending
    sort(bag.begin(), bag.end());

    int bagSize = bag.size();
    for(int i = 0; i < bagSize; i++)
    {
        // Push all jewels those bag can contain
        for(int j = 0; j < jewel.size(); j++)
        {
            if (jewel.top().first <= bag[i])
            {
                containLimit.push(jewel.top().second);
                jewel.pop();
            }
            // No more jewels to contain
            else break;
        }

        // Contain most valuable jewel
        if(!containLimit.empty())
        {
            ans += containLimit.top();
            containLimit.pop();
        }
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

한 달만에 재도전하여 손쉽게 해결한 문제이다.
성장하고 있음을 느낀다!🥊 🥊 🥊
보석은 훔치지 말자.