5주차(그리디) - [C++]백준1202 보석 도둑

02 Apr 2022 in Study on Algorithm

백준1202 보석 도둑 링크

문제

예제 입력

---

코드

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

int N, K;
vector<int> poket;
vector<pair<int, int>> arr;
priority_queue <int> heap;
long long ans = 0;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> N >> K;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        arr.push_back({ a, b });
    }
    for (int i = 0; i < K; i++) {
        cin >> a;
        poket.push_back(a);
    }
    sort(arr.begin(), arr.end());
    sort(poket.begin(), poket.end());

    // 각 가방에 맞는 용량의 보석중에 비싼 것
    int idx = 0;
    for (auto bag_w : poket)
    {
        while (idx < N && arr[idx].first <= bag_w)
            heap.push(arr[idx++].second);
        if (!heap.empty())
        {
            ans += heap.top();
            heap.pop();
        }
    }
    cout << ans << "\n";
}

설명

이 문제는 여러개의 가방과 다양한 보석이 존재하는데 가방 하나당 1개의 보석만 넣어서 보석 가격의 합의 최댓값을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 Queue를 사용하여 구현했습니다. 가방과 보석의 정보를 입력 받아 둘다 용량을 기준으로 정렬하여 가방의 용량이 작은 것부터 담을 수 있는 보석을 전부 다 힙(heap)에 담고 이제는 보석이 커서 담지 못할때 그중에서 제일 비싼 것을 힙(heap)에서 POP하여 가방에 넣어줍니다. 이렇게 제한된 용량에서 최선의 선택을 순간하여 답을 구합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용
-priority_queue<자료형> 변수명; : 우선순위 큐(힙) 자료구조 사용

---

결과