방과후
ALGORITHM NOTE약 1분

BOJ 1202 - 보석 도둑

보석 털?자!

#algorithm#boj#gold#data-structures#greedy#sorting#priority-queue
아카이브로 돌아가기

문제 링크

문제

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

상덕이가 털 보석점에는 보석이 총 NN개 있다. 각 보석은 무게 MiM_i와 가격 ViV_i를 가지고 있다. 상덕이는 가방을 KK개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 CiC_i이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

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

입력

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

다음 NN개 줄에는 각 보석의 정보 MiM_i와 ViV_i가 주어진다. (0≤Mi,Vi≤1,000,000)(0 \le M_i, V_i \le 1{,}000{,}000)

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

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

출력

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

풀이

가방을 아무 순서로 보는 대신, 담을 수 있는 무게가 작은 가방부터 차례대로 처리하면 구조가 단순해진다. 현재 가방에 들어갈 수 있는 보석들만 모아 두고, 그중 가장 비싼 것을 하나 꺼내면 항상 최선이다.

코드에서는 보석을 무게 오름차순으로, 가방도 최대 허용 무게 오름차순으로 정렬한다. 가방 하나를 볼 때마다 아직 처리하지 않은 보석 중에서 현재 가방에 들어갈 수 있는 모든 보석의 가격을 최대 힙에 넣는다. 그리고 힙의 맨 위, 즉 가장 비싼 보석 하나를 꺼내 현재 가방에 담는다.

한 번 힙에 들어간 보석은 이후 더 큰 가방에도 들어갈 수 있으므로, 작은 가방부터 순서대로 처리하는 전략이 자연스럽다. 이렇게 하면 각 가방에 대해 '지금까지 들어갈 수 있었던 후보 중 최고가'를 빠르게 고를 수 있다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Jewel implements Comparable<Jewel> {
        int weight, price;
        Jewel(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
 
        @Override
        public int compareTo(Jewel o) {
            if (this.weight == o.weight) return o.price - this.price;
            return this.weight - o.weight;
        }
    }
 
    static class Bag implements Comparable<Bag> {
        int maxWeight;
        Bag(int maxWeight) {
            this.maxWeight = maxWeight;
        }
 
        @Override
        public int compareTo(Bag o) {
            return this.maxWeight - o.maxWeight;
        }
    }
 
    static int N, K;
    static List<Jewel> jewels = new ArrayList<>();
    static List<Bag> bags = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            jewels.add(new Jewel(m, v));
        }
        Collections.sort(jewels);
 
        for (int i = 0; i < K; i++) {
            int c = Integer.parseInt(br.readLine());
            bags.add(new Bag(c));
        }
        Collections.sort(bags);
 
        System.out.println(solve());
    }
 
    static long solve() {
        long ans = 0;
        int idx = 0;
 
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (Bag bag : bags) {
            while (idx < N && jewels.get(idx).weight <= bag.maxWeight) {
                pq.offer(jewels.get(idx).price);
                idx++;
            }
 
            if (!pq.isEmpty())
                ans += pq.poll();
        }
 
        return ans;
    }
}

복잡도

  • 시간 복잡도: O((N+K)log⁡N)O((N + K) \log N)
  • 공간 복잡도: O(N)O(N)

마무리

보석을 무게순으로 밀어 넣고, 가방마다 그 순간 담을 수 있는 최고가만 고르면 된다. 정렬과 최대 힙 조합이 아주 정석적으로 들어맞는 문제다.