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

1202번: 보석 도둑

문제

코드

/**
 * baekjoon - 1202
 * data structure, greedy, sorting, priority queue
 */

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

vector<pair<int,int>> jewel; // 무게, 가격
vector<int> bag; // 가방

int main(){
    fio;
    //input
    int n, k, m, v, c;
    cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> m >> v;
        jewel.push_back(make_pair(m, v));
    }

    for (int i = 0 ; i < k; i++){
        cin >> c;
        bag.push_back(c);
    }

    // sol
    int cnt = 0;
    long long result = 0;
    int index = 0;
    priority_queue<int> pq;

    // sorting
    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    // greedy
    for (int i = 0; i < k; i++){
        while(index < n && jewel[index].first <= bag[i]){ // 해당 가방에 넣을 수 있는 보석 모두 넣기
            pq.push(jewel[index++].second);
        }

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

    cout << result;

    return 0;
}

해설

해당 문제는 주어진 입력값을 정렬하여 greedy를 이용해 해결해주는 문항이다.

1. 입력값을 vector를 이용해 저장해준다. 무게와 가격은 pair를 이용해 저장해주어 후에 둘을 같이 이용할 수 있도록 해준다.

vector<pair<int,int>> jewel; // 무게, 가격
vector<int> bag; // 가방

1. 두 배열을 오름차 순으로 정렬해준다. 이 때 sort함수를 이용해준다.

2. greedy 알고리즘과 우선순위 큐를 이용해 해당 문제를 해결한다.

   정렬된 가방 배열을 순서대로 받아 해당 가방에 넣을 수 있는 보석들을 우선순위 큐에 넣어준다. 가방 무게보다 작은 보석들을 우선순위 큐에 넣어주면 무거운 것이 계속 top에 남게 되어 주어진 가방에 못들어가게 되면 다음 가방에 넣을 수 있는 우선권을 갖게 된다.

3. 들어갈 수 있는 보석을 다 넣은 후, 우선순위 큐의 top에 존재하는 원소를 빼내 최종 결과값에 추가해준다. —> 이 때, 자료형을 long long으로 해주어 최종 결과값이 오버플로우가 나지 않도록 한다. (최종 제출 때 int로 사용하여 오류 발생)