백준 알고리즘 1202번: 보석 도둑

문제 정보

---

 

1202번: 보석 도둑

 

핵심

---

요약

각 보석들(N개)의 무게 및 가격이 존재한다

가방들(K개)에는 담을 수 있는 최대 무게가 존재한다

각 가방에는 보석을 하나씩만 담을 수 있음

-> 가방들로 담을 수 있는 보석 가격 합의 최대를 구하기 

 

생각한 방법

단순히 무게만 가지고, 가방이 담을 수 있는 최소 무게의 보석을 택하는 것이 아닌 최대의 가격을 함께 생각해서 담아야 함

또한, 가방의 무게를 정렬해서 구해야 왼쪽의 케이스를 해결할 수 있음

 

힙에 정렬된 요소들 중에서 선택한 가방에 담을수 있는 것들만 뽑아서 다시 최대 Heap에 넣는다

이 때의 최대 Heap은 가격 순 내림차순 정렬한다

 

3. 보석들을 무게 순으로 최소 Heap을 구성하여 담는다

3-1. 가방에 담을 수 있는 무게와 비교하여 Heap에서 담을 수 있는 보석들을 꺼내서 최대 Heap(가격 순)에 다시 담는다

3-2. 이렇게 담은 최대 Heap의 루트 값은 가질 수 있는 최대 가격의 보석이다. 이를 pop하여 결과에 추가한다.

3-3. 나머지는 놔둔다. 가방을 무게 순으로 정렬했기 때문에 다음 가방에서도 담을 수 있는 보석들이다

 

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Item> queue = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            queue.add(new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

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

        Queue<Item> steals = new PriorityQueue<>(((o1, o2) -> o2.price - o1.price));
        long result = 0;
        for(int i=0; i<K; i++) {
            int weight = bag[i];

            while(!queue.isEmpty() && queue.peek().weight <= weight) {
                steals.add(queue.poll());
            }
            if(!steals.isEmpty()) {
                result += steals.poll().price;
            }
        }
        System.out.println(result);
    }
}

class Item {
    public final int weight;
    public final int price;

    public Item(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}

 

 

Source Code on GitHub

---