[백준] 1202번 : 보석 도둑 - C++ / JAVA

백준 1202 : 보석 도둑

등급 : Gold II

1202번: 보석 도둑 (acmicpc.net)

1202번: 보석 도둑

사용 알고리즘 : Greedy, Sorting

사용 자료구조 : Deque, Priority_Queue

 

정렬과 우선순위 큐를 이용해 푸는 그리디 문제였다.

가방의 크기와 보석을 무게순으로 오름차순으로 정렬하고, 가방을 하나씩 선택해 현재 가방의 허용 무게 내의 보석을 선택.

현재 가방에 들어갈 수 있는 보석의 가격을 우선순위 큐에 입력.

이후 현재 가방에 맞는 최고 보석 가격을 선택하고, 다음 가방으로 변경.

위의 아이디어만 떠올리면 풀 수 있는 문제이다.

<hide/>
#include <iostream>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;
#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k, m, v;
    ll c;
    ll ans = 0;
    deque <pair <int, int>> jewel;
    deque <ll> weight;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> m >> v;
        jewel.push_back({ m, v });
    }
    for (int i = 0; i < k; i++)
    {
        cin >> c;
        weight.push_back(c);
    }
    sort(jewel.begin(), jewel.end());
    sort(weight.begin(), weight.end());
    priority_queue <int> pq;
    while (!weight.empty())
    {
        ll cur_weight = weight.front();
        weight.pop_front();
        while (!jewel.empty() && jewel.front().first <= cur_weight)
        {
            pq.push(jewel.front().second);
            jewel.pop_front();
        }
        if (!pq.empty())
        {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        class jewel_info
        {
            int m;
            int v;

            jewel_info(int m, int v)
            {
                this.m = m;
                this.v = v;
            }
        }
        int n, k, m, v;
        long c;
        long ans = 0;
        List <jewel_info> jewel = new LinkedList<>();
        List <Long> weight = new LinkedList<>();
        PriorityQueue <Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=0; i<n; i++)
        {
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            jewel.add(new jewel_info(m, v));
        }
        for(int i=0; i<k; i++)
        {
            c = Integer.parseInt(br.readLine());
            weight.add(c);
        }
        Collections.sort(jewel, (p1, p2)->
        {
            return p1.m - p2.m;
        });
        Collections.sort(weight);
        while(!weight.isEmpty())
        {
            long cur_weight = weight.get(0);
            weight.remove(0);
            while(!jewel.isEmpty() && jewel.get(0).m <= cur_weight)
            {
                pq.add(jewel.get(0).v);
                jewel.remove(0);
            }
            if(!pq.isEmpty())
            {
                ans += pq.poll();
            }
        }
        System.out.println(ans);
    }
}