[백준 1202] 보석 도둑 - JAVA

문제

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

상덕이가 털 보석점에는 보석이 총 $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)$

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

출력

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

---

접근 방법

처음 접근을 했을 때 그리디인 것은 인지하고 있었습니다.

• 각각의 가방에 담을 수 있는 무게의 최대치 내의 보석 무게를 가지는 보석들 중에서 가장 가치 있는 것을 가방에 담아야 합니다.
• 이 작업을 가방이 가장 작은 순서부터 진행합니다.

이론적으로는 인지했지만 문제가 있었습니다.

• 보석에 대한 정렬을 어떻게 해야되는가
  • 무게를 기준으로 정렬해야될까?
  • 가치를 기준으로 정렬해야될까?

보석을 두 가지 방식으로 모두 정렬해보고 가방 또한 작은 순으로 정렬했지만
보석과 가방의 정렬만으로는 문제를 해결할 수 없고
추가적인 로직을 통해 작은 가방부터 담을 수 있는 가장 가치있는 보석을 넣어야 합니다.

거기에 위와 같은 로직을 $O(NlogN + KlogK)$ 이내로 수행해야 문제를 해결할 수 있는데
처음에는 그런 방법이 전혀 떠오르지 않았습니다.

그러다 새로운 임시 큐를 사용해서
보석을 무게 순으로 오름차순 정렬을 하고
현재 가방에 들어갈 수 있는 가치들을 jewelPQ에서 모두 꺼내오면
jewelPQ를 한 번만 순회하고 문제를 해결할 수 있겠다고 판단을 해서 구현을 했고
문제를 해결할 수 있었습니다.

---

코드

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


class Jewel implements Comparable<Jewel> {
    int m;
    int v;

    public Jewel (int m, int v) {
        this.m = m;
        this.v = v;
    }

    @Override
    public int compareTo(Jewel o) {
        if (this.m != o.m) return Integer.compare(this.m, o.m);
        return Integer.compare(o.v, this.v);
    }
}


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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        PriorityQueue<Jewel> jewelPQ  = new PriorityQueue<>();
        int[] bags = new int[K];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewelPQ.offer(new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        for (int i = 0; i < K ; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(bags);

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        long answer = 0;

        for (int bag : bags) {
            while (!jewelPQ.isEmpty() && jewelPQ.peek().m <= bag) {
                pq.offer(jewelPQ.poll().v);
            }

            if (!pq.isEmpty()) {
                answer += pq.poll();
            }
        }

        System.out.println(answer);
    }
}