[C++][백준 BOJ]1202_보석 도둑.

문제 번호

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

1202번: 보석 도둑

 

 

알고리즘 분류

 그리디(greedy), 우선순위 큐(priority_queue)

 

문제 풀이

 문제에서 주어진 가방의 크기들을 오름차순으로 정렬한다. 문제에서 주어진 보석들 또한 무게를 기준으로 오름차순으로 정렬한다. 우리는 가방에 1개의 보석만 넣을 수 있기 때문에 넣을 수 있는 보석들중 가장 비싼 보석을 넣어야한다.

그래서 Max Heap을 이용하여 각 가방에 넣을 수 있는 최대가치의 보석을 구할것이다.

 

문제에서 주어진 내용들을 정렬한다.

// MAX HEAP pq
    priority_queue<int, vector<int>, less<int>> pq;
    // 가방을 무게 오름차순으로 정렬한다.
    sort(bag.begin(), bag.end());
    // 보석을 무게 오름차순으로 정렬한다.
    sort(jewelry.begin(), jewelry.end());

각 가방에 넣을 수 있는 최대 가치의 보석들을 넣는다.

  int j = 0;
    for (int i = 0; i < bag.size(); i++)
    {
        // 가방에 담을 수 있는 모든 보석을 담는다.
        for (; j < jewelry.size(); j++)
        {
            if (jewelry[j].first <= bag[i])
                pq.push(jewelry[j].second);
            else
                break;
        }

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

전체 코드

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

vector<int> bag;
vector<pair<int, int>> jewelry;

// 무게 오름차순정렬, 무게가 같으면 가치 내림차순 정렬.
bool compare(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first)
        return a.second > b.second;

    return a.first < b.first;
}

void Insert(int N, int K)
{
    // 보석의 무게와 가치를 입력한다.
    for (int i = 0; i < N; i++)
    {
        int M;
        cin >> M;
        int V;
        cin >> V;
        jewelry.push_back({M, V});
    }

    // 가방의 크기를 입력한다.
    for (int i = 0; i < K; i++)
    {
        int C;
        cin >> C;
        bag.push_back(C);
    }
}

long long Solution()
{
    long long answer = 0;

    // MAX HEAP pq
    priority_queue<int, vector<int>, less<int>> pq;
    // 가방을 무게 오름차순으로 정렬한다.
    sort(bag.begin(), bag.end());
    // 보석을 무게 오름차순으로 정렬한다.
    sort(jewelry.begin(), jewelry.end());

    int j = 0;
    for (int i = 0; i < bag.size(); i++)
    {
        // 가방에 담을 수 있는 모든 보석을 담는다.
        for (; j < jewelry.size(); j++)
        {
            if (jewelry[j].first <= bag[i])
                pq.push(jewelry[j].second);
            else
                break;
        }

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

    return answer;
}

int main()
{
    int N, K;
    cin >> N >> K;
    Insert(N, K);
    cout << Solution();

    return 0;
}

 

특이사항

 문제에서 주어진 조건에 의하면 결과값은 int 의 범윌르 넘을 수 있다. 따라서 long long을 사용하여 정답을 처리했다.

첫 시도에는 시간초과가 나왔는데 다른분들의 질문과 풀이를 참고하여 Max Heap을 사용하는 방법을 알아냈다. 그리디를 풀면서 자료구조나 STL 사용에 대해서 익숙해지고 더 공부해야겠다.