[백준/C++] #1202 보석 도둑 (Greedy)

문제

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

 

구상

k개의 가방을 가지고 있고, 각 가방에 최대 무게 c만큼의 보석 1개를 넣을 수 있는 문제였다. 이때, 가방에 넣어서 훔칠 보석의 최대 가격을 구하는 문제였는데, c무게보다 같거나 가벼운 보석중에 가장 가치가 큰 보석을 하나씩 골라 가방을 하나씩 채워나가면 된다.  

 

그러기 위해서는 우선, 보석 무게와 가방 무게를 오름차순으로 정렬해야 했다. 이후, 가방을 하나씩 돌면서, 가방 무게보다 작은 무게의 보석들을 보면서 가치 하나하나를 max_heap에 넣은뒤, 가방 무게를 초과하기 직전 상태에서 max_heap의 top 가치를 total_value에 넣어야 한다. 중복되는 보석을 max_heap에 넣으면 안되기에 넣을 보석의 인덱스를 가방에 맞는 보석 탐색하는 for문 밖으로 빼어 다음 for문에서는 가능한 다음 보석부터 max_heap에 넣을 수 있도록 하였다. 

 

알고리즘

현재 가방의 무게에 맞는 보석들의 가치가 전부 들어있는 가방에서 가능한 가장 가치가 높은 (최적의) 보석을 고르고 가방에 담는 과정을 반복하기에, greedy 알고리즘을 사용한다고 할 수 있다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define endl "\n"
using namespace std;
/*
1202 보석도둑 
*/

int N, K; // 보석의 개수, 가방 개수

vector<pair<int, int>> jewel(MAX); // 보석 정보
vector<int> bag(MAX); // 가방 무게

void solution() {
    // 작은 무게의 보석, 가방부터 처리하기 위해 정렬
    sort(jewel.begin(), jewel.end()); // 보석을 무게 기준으로 정렬
    sort(bag.begin(), bag.end()); // 가방을 무게 기준으로 정렬

    priority_queue<int> max_heap; // 가치가 가장 큰 보석이 top으로 오도록. (기본이 내림차순)
    int jewel_index = 0; // 밖으로 빼서 보석 중복되지 않도록
    long long total_value = 0; // C ≤ 100,000,000 들의 합이기에

    for (int i = 0; i < K; ++i) { // 가방 K개 채우기
        while (jewel_index < N && jewel[jewel_index].first <= bag[i]) { // 보석 무게 <= 가방 무게일 때 
            max_heap.push(jewel[jewel_index].second); // 가치 넣기
            ++jewel_index; // 인덱스 이동
        }

        if (!max_heap.empty()) { // 힙에 아직 존재한다면
            total_value += max_heap.top(); // 가능한 경우들 중 가치 가장 큰거 가방에 넣기 -> GREEDY
            max_heap.pop(); // top인거 pop
        }
    }

    cout << total_value;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N >> K; // 보석 개수, 가방 개수
    jewel.resize(N);
    bag.resize(K);

    for (int i = 0; i < N; i++) {
        cin >> jewel[i].first >> jewel[i].second; // 무게, 가격
    }

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

    // 로직
    solution();

    return 0;

}