BOJ 1202 보석 도둑

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

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 $C_i$이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N과 K가 주어진다. $(1 ≤ N, K ≤ 300,000)$

다음 N개 줄에는 각 보석의 정보 $M_i$와 $V_i$가 주어진다. $(0 ≤ M_i, V_i ≤ 1,000,000)$

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 $C_i$가 주어진다. $(1 ≤ C_i ≤ 100,000,000)$

모든 숫자는 양의 정수이다.

---

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

---

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

---

힌트

두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Jewel implements Comparable<Jewel> {
        int weight, price;

        public Jewel(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Jewel o) {
            return weight - o.weight;
        }
    }

    /**
     * 1. 보석과 가방을 낮은 무게 순으로 뽑을 수 있도록 각각 우선순위 큐에 넣는다
     * 2. 가장 낮은 무게의 가방에 담을 수 있는 보석을 검사해 가장 높은 가치의 보석을 담는다
     * 2-1. 담을 수 있는 가장 높은 가치의 보석을 검사할 때, 탈락한 보석의 가치는 또 다른 우선순위 큐에 넣는다
     * 3. 그 다음 순서의 가방에 담을 수 있는 가장 높은 가치의 보석을 검사하고,
     *    그 보석의 가치와 탈락한 보석의 가치 우선순위 큐에서 peek한 가치 중 큰 것을 가장 높은 가치의 보석으로 결정
     * 4. 3번을 반복
     * 5. 모든 보석을 검사 후 가방에 넣고도 가방이 남는다면, 탈락한 보석의 가치 우선순위 큐에서 차례로 poll 해서 가방을 채움
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
        PriorityQueue<Jewel> jewels = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewels.offer(new Jewel(
                    Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())
            ));
        }

        PriorityQueue<Integer> bags = new PriorityQueue<>();
        for (int i = 0; i < K; i++) bags.offer(Integer.parseInt(br.readLine()));

        long answer = 0;
        PriorityQueue<Integer> leftJewels = new PriorityQueue<>(Collections.reverseOrder());
        while (!bags.isEmpty() && !jewels.isEmpty()) {
            int maxWeight = bags.poll(), maxPrice = 0;
            while (!jewels.isEmpty() && jewels.peek().weight <= maxWeight) {
                Jewel check = jewels.poll();
                if(maxPrice < check.price) {
                    if (maxPrice > 0) leftJewels.offer(maxPrice);
                    maxPrice = check.price;
                } else leftJewels.offer(check.price);
            }
            if(!leftJewels.isEmpty() && leftJewels.peek() > maxPrice) {
                answer += leftJewels.poll();
                leftJewels.offer(maxPrice);
            } else answer += maxPrice;
        }

        while (!bags.isEmpty() && !leftJewels.isEmpty()) {
            bags.poll();
            answer += leftJewels.poll();
        }

        System.out.println(answer);
    }
}