[백준] 1202 보석 도둑 java

문제

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

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

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

출력

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

풀이

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

class Jewel implements Comparable<Jewel>{
    int weight;
    int cost;

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


    @Override
    public int compareTo(Jewel o) {
        int comp = Integer.compare(weight, o.weight);
        if(comp == 0) {
            return Integer.compare(cost, o.cost);
        }
        return comp;
    }
}

public class BOJ1202 {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, k, m, v, c;
    static long res;
    static Jewel[] jewels;
    static int[] bags;
    static PriorityQueue<Jewel> picked;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.println(res);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        k = stoi(st.nextToken());
        jewels = new Jewel[n];
        bags = new int[k];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            m = stoi(st.nextToken());
            v = stoi(st.nextToken());
            jewels[i] = new Jewel(m, v);
        }

        for (int i = 0; i < k; i++) {
            c = stoi(br.readLine());
            bags[i] = c;
        }

    }

    static void solve() {
        /*
        시간복잡도는 O(K log K)가 나와야 한다.
        보석 개수 N 가방 개수 K
        보석의 무게 M 보석의 가격 V
        가방의 무게 C
        각각 가방에 들어갈 수 있는 무게의 보석 중 최댓값을 넣어주면 된다.
        큰 가방은 넣을 수 있는게 많아 작은 것 부터 구해야함. 가방을 오름차순 정렬해서 작은 가방부터 탐색한다.
        보석도 무게순, 같다면 가격순으로 오름차순 정렬
        가방 하나씩 탐색 = 선형탐색 T(K)
        가방에 들어가는 보석 = 작은 것 부터 선정 T(N)
        가방에 들어가는 보석 중 최댓값 탐색 = 최대힙으로 맨 앞에 것 선정 T()
         */

        //가방 무게순 오름차순 정렬, 보석 무게순, 무게가 같다면 가격순 정렬
        Arrays.sort(bags);
        Arrays.sort(jewels);
        picked = new PriorityQueue<>(new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                return Integer.compare(o2.cost, o1.cost);
            }
        });

        //작은 가방 부터 하나씩
        int idx = 0;
        for (int i = 0; i < k; i++) {
            //가방에 들어가는 보석 찾기
            while(idx < n) {
                //가방의 무게안에 들어가는 보석인가?
                if(jewels[idx].weight <= bags[i]) {
                    picked.add(jewels[idx]);
                } else {
                    break;
                }
                idx++;
            }

            if(!picked.isEmpty()) {
                //최대값 더하기
                res += picked.poll().cost;
            }
        }
    }


    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}

우선순위 큐와 정렬을 사용한 자료구조 문제이다.

 

일단 가방마다 넣을 수 있는 무게의 보석 중 가장 큰 값을 찾아야 한다. 그러러면 들어갈 경우의 수가 작은 무게가 작은 가방부터 골라야 한다. 그러므로 가방의 무게가 담긴 배열과 보석도 무게별로 보아야 하니 보석 배열도 동일하게 오름차순 정렬을 해주면 된다.

 

그리고 작은 가방부터 들어갈 수 있는 보석을 탐색해서 그 중 가격이 제일 비싼 보석대로 정렬되어야 하니 우선순위 큐를 사용했다. 그렇게 하면 다 넣고나서 가방에 들어갈 보석을 꺼낼 때 한번만 꺼내주면 된다.

 

그리고 어처피 가방의 무게는 계속 늘어나고 그 전에 담았던 보석도 그대로 넣을 수 있으니 탐색을 멈췄던 차례의 보석부터 다시 탐색해주면서 반복하면 답을 구할 수 있게된다.