[백준] 1202번 - 보석 도둑 [Java]

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

 

[백준] 1202번 - 보석 도둑 [Java]

[백준] 1202번 - 보석 도둑 [Java]

---

1.  아이디어

 

그리디 알고리즘으로 해결할 수 있다.

가방들을 크기가 작은 순으로 정렬한 후 각 가방에 담을 수 있는 무게의 보석들 중 가장 가격이 높은 보석을 담는 과정을 반복하면 된다.

---

2. 문제풀이

 

보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐와 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.

입력을 받아 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에 담은 후 각 가방에 대해 해당 가방에 담을 수 있는 무게의 보석들을 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에서 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static class Jewel {
        int m;
        int v;

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

    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());
        int K = Integer.parseInt(st.nextToken());

        // 무게에 대한 오름차순 정렬
        PriorityQueue<Jewel> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.m, o2.m));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            pq.add(new Jewel(m, v));
        }

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

        // 가격에 대한 내림차순 정렬
        PriorityQueue<Jewel> pq2 = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.v, o1.v));
        long sum = 0;
        for (int knapsack : knapsacks) {
            while (!pq.isEmpty() && pq.peek().m <= knapsack) {
                pq2.add(pq.remove());
            }

            if (pq2.isEmpty()) continue;

            sum += pq2.remove().v;
        }

        System.out.println(sum);
    }
}

---

4. 후기