백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명

1. 용량이 적은 가방부터 채운다.
2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다.
3. 남은 가방에 대해 1-2를 반복한다.

---

1. 용량이 작은 가방부터 채운다.

 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다.

 

2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다.

 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의 용량이 4라고 하면, 3번째 보석까지 현재 가방에 담을 수 있다.

 이 중에서 가장 가격이 높은 보석을 알아내기 위해 가격을 기준으로하는 우선순위 큐에 [0]~[2] 번째 보석을 모두 넣는다. 그리고 pop하여 가격이 가장 높은 것([0] 번 보석)을 담는다. 우선순위 큐에는 아직 나머지 2개 보석([1], [2] 번 보석)이 남아있다. 이 보석들이 추후에 더 큰 용량의 가방에 들어갈 수 있다.

 이제 다음으로 용량이 작은 용량 8인 가방을 채울 차례라고 하자. 용량이 8인 가방에 담을 수 있는 보석들은 파란색으로 표시한 만큼이고, 이것들 중에 가장 가격이 높은 것을 알아내기 위해 이 보석들을 우선순위 큐에담는다. 이미 1, 2, 3은 넣었으므로 추가된 7, 8만 담아주면 된다.

 

3. 남은 가방에 대해 1-2를 반복한다.

 이렇게 용량이 적은 가방부터 하나씩 채워나가면 된다.

 

---

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

using namespace std;

priority_queue<int, vector<int>, less<int>> max_pq;

int N, K;
int p;
vector<pair<int, int>> gems;
vector<int> backpacks;

int fillBackpack(int index) {
    while (p < N && gems[p].first <= backpacks[index])  {    // 배낭에 들어갈 수 있는 보석 전부 우선순위큐에 삽입
        max_pq.push(gems[p++].second);
    }
    
    if (max_pq.empty()) {
        return 0;
    }
    else {
        int ret = max_pq.top(); max_pq.pop();   // 들어갈 수 있는 보석 중 최대 가치인 것을 담음
    return ret;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int w, v, c;
	
    cin >> N >> K;
    
    for (int i = 0; i < N; i++) {
        cin >> w >> v;
        gems.push_back({w, v});
    }
    
    for (int i = 0; i < K; i++) {
        cin >> c;
        backpacks.push_back(c);
    }
    
    sort(gems.begin(), gems.end());             // 무게 오름차순 정렬
    sort(backpacks.begin(), backpacks.end());   // 용량 오름차순 정렬
    
    long long result = 0;
    
    for (int i = 0; i< K; i++) {
        result += (long long)fillBackpack(i);              // 배낭을 순서대로 채움
    }
    
    cout << result;

    return 0;
}