1202 보석 도둑

1202. 보석 도둑 / c++ / Gold2 / 55분

문제

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

1. N개의 보석과 K개의 가방이 주어진다. (1 <= N,K <= 300’000)
2. 각 보석은 M의 무개와 V의 가치를 지닌다. (0 <= M,V <= 1’000’000)
3. 각 가방은 최대 C의 무게까지 담을 수 있다. (1 <= C <= 100’000’000)
4. 하나의 가방에 하나의 보석밖에 넣지 못할 때, 담을 수 있는 보석의 최대 가치는?

접근 방식

자료구조, 그리디, 우선순위 큐

1. 매번 가치가 최고인 것을 골라야 하니 그리디 알고리즘을 이용할 수 있다.
2. 그리디 = 우선순위 큐 라고 봐도 될 정도로 활용성이 좋아서 우선순위 큐를 이용했다.
3. 가방을 무게가 작은순으로 순회하면서, 자신보다 무게가 가벼운 보석들을 우선순위 큐에 다 담는다.
4. 그리고 그 중 가장 가치가 높은 보석을 고른다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int N, K, M, V;

vector<pair<int, int>> jewels;
vector<int> bags;
unsigned long long answer = 0;
priority_queue<int> trashBag;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;

    while (N-- > 0)
    {
        cin >> M >> V;
        jewels.push_back({ M, V });
    }

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

    while (K-- > 0)
    {
        cin >> M;
        bags.push_back(M);
    }

    sort(bags.begin(), bags.end());

    int jewelsPos = 0;
    for (int i = 0; i < bags.size(); ++i)
    {
        while (jewelsPos < jewels.size())
        {
            if (jewels[jewelsPos].first <= bags[i])
            {
                trashBag.push(jewels[jewelsPos++].second);
            }
            else break;
        }
        if (!trashBag.empty())
        {
            answer += trashBag.top(); trashBag.pop();
        }
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 처음엔 보석과 가방을 모두 우선순위 큐로 처리했었다. 그럴 필요가 없었다. 꼭 필요한 것만 우선순위 큐를 사용하고, 자료구조를 남용하지 말자.
2. ‘현재 가방보다 무게가 가장 작은 것 중 가장 높은 가치의 보석’ 이 이번 문제의 핵심이었다. 핵심 키워드를 정확히 정해놓으면 문제 풀기가 더 수월할 것 같다.