백준 1202 - 보석 도둑

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 보석의 무게와 가치가 주어지고 K개의 가방의 용량이 주어진다.

가져갈 수 있는 보석의 최대 가치를 구해야 한다.

 

해당 문제가 냅색과 유사하다고 생각했다.

하지만, 가방이 여러 개이며 용량보다 작은 보석은 무엇이든 담을 수 있으며 최대 1개까지만 담을 수 있다.

따라서, dp를 통해 어떠한 가방에 어떤 보석을 담을지 기록하는 것은 힘들다고 생각했다.

 

해당 문제는 그리디를 이용하면 된다.

우선, 보석과 가방을 무게순으로 정렬한다.

가방을 기준으로 현재 가방에 담을 수 있는 보석을 모두 pq에 넣는다.

이때, pq는 가치가 높은 보석의 우선순위가 높도록 설정한다.

이후, pq에서 하나를 뽑으면 해당 가방에 담을 수 있는 무게에서 가장 가치 높은 보석을 담을 수 있다.

이를 K개의 가방에 대해 진행하면 모든 가방에 담을 수 있는 최대 가치를 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, K;
vector<pair<int,int>> jewels;
vector<int> backpacks;
priority_queue<int> pq;

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

    cin >> N >> K;
    backpacks.resize(K);

    for (int i = 0; i < N; i++)
    {
        int m, v;
        cin >> m >> v;
        jewels.push_back({ m,v });
    }

    for (int i = 0; i < K; i++)
    {
        cin >> backpacks[i];
    }

    sort(jewels.begin(), jewels.end());
    sort(backpacks.begin(), backpacks.end());

    int idx = 0;
    long long sum = 0;

    for (int i = 0; i < K; i++) 
    {
        while (idx < N && jewels[idx].first <= backpacks[i])
        {
            pq.push(jewels[idx].second);
            idx++;
        }

        if (!pq.empty()) 
        {
            sum += pq.top();
            pq.pop();
        }
    }

    cout << sum;

    return 0;
}

---