[백준 - G2] 1202. 보석 도둑

문제 링크

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

문제

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

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 \(Mi\)와 가격 \(Vi\)를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 \(Ci\)이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

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

입력

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

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

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

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

출력

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

---

아이디어

1. 보석은 무게 기준 낮은 것(오름차순), 무게가 같으면 가격이 높은 것(내림차순)을 선택한다.
2. 가방은 무게가 작은 것(오름차순)부터 선택한다.
3. 각 가방에 들어갈 수 있는 보석만 PQ에 넣고, 그 중 가격이 최대인 것(여기서 한번 더 정렬! 내림차순)을 선택한다.

처음에 보석을 PQ에 넣고 1번 정렬만 했었는데 시간초과와 오답이 반복됐다.
아래처럼 보석 전체를 뽑아서 배낭을 조회하면 모든 경우의 수를 반복할 수 있기 때문에, \(O(N × K)\)가 될 수 있으므로 주의할 것!

아래는 틀린 로직!

int price = 0;
int[] result = new int[K];
while (!jewel.isEmpty()) {
    Node curr = jewel.poll();
    for (int i = 0; i < K; i++) {
        if (result[i] < curr.v && curr.m <= bags[i]) {
            result[i] = curr.v;
        }
    }
}

제출 코드

• 시간 복잡도
  • 보석 정렬 \(O(NlogN)\) + 가방 정렬 \(O(KlogK)\) + 보석 힙 추가/삭제 \(O(NlogN)\) = \(O((N+K) log N)\)
• N <= 300,000, K <= 300,000 이므로 \(O(NlogN)\) 까지 가능하다. \(O(N × K)\) ≈ \( 9×10^{10} \) 이므로 불가능하다.

펼치기

class Main {

    static class Node implements Comparable<Node> {
        int m, v;

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

        @Override
        public int compareTo(Node o) {
            int cmp = Integer.compare(this.m, o.m); // 무게는 낮지만, 가격은 높은 것
            if (cmp == 0) {
                return Integer.compare(o.v, this.v);
            }
            return cmp;
        }

        @Override
        public String toString() {
            return "(" + m + ", " + v + ")";
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);

        Node[] jewel = new Node[N];
        for (int i = 0; i < N; i++) {
            split = br.readLine().split(" ");

            int M = Integer.parseInt(split[0]); // 무게
            int V = Integer.parseInt(split[1]); // 가격
            jewel[i] = new Node(M, V);

        }

        Arrays.sort(jewel, Comparator.comparingInt(a -> a.m));

        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            int C = Integer.parseInt(br.readLine()); // 최대 무게
            bags[i] = C;
        }

        Arrays.sort(bags);
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> b.v - a.v); // 가격 내림차순

        long price = 0;
        int idx = 0;
        for (int i = 0; i < K; i++) {
            while (idx < N && jewel[idx].m <= bags[i]) {
                pq.offer(jewel[idx++]);
            }

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

        System.out.println(price);
    }

}