자바(백준) 1202 보석 도둑

오답 노트 & 새로 알게 된 점

 

이 문제는 개인적으로 정말 어려웠다.

처음에 그냥 완탐은 TLE가 날 것 같다. 이 정도만 알고 있었다.

TLE가 나면 이제 시간 복잡도를 줄이면서 풀 생각을 해야하는데 풀이법이 떠오르지 않았다.

 

풀이법을 설명하자면,

보석이 들어있는 배열을 가격 순으로 오름차순 정렬한다. 

또한, 가방이 들어있는 배열을 무게 순으로 오름차순 정렬한다.

 

그리고 pro 메서드를 보면 while문이 있다.

while문에서는 가방 배열을 기준으로, jew 배열을 탐색한다.

거기서 가방보다 무게가 낮은 보석들을 모두(가방에 담을 수 없는 보석을 만날 때까지) pq에 넣는다. 이 때, pq는 오름차순 정렬이다.

 

그렇다면 무게가 2인 가방(2가방이라함) 65와 99의 보석을 모두 담을 수 있다.

다만 가방 한 개에는 보석 한개만 담을 수 있다. 그래서 2가방에는 99보석이 들어가게 된다.

 

이제 i = 1이 되면 23보석이 들어온다.

그렇다면 어떻게 10가방에 65보석이 들어갈까?

65는 이미 2가방에 들어갈 수 있어서 우선순위 큐에 들어가있다.

여기서 bagInfo는 오름차순이다. 즉, 이미 2가방에 들어가 있는 65는 다음 가방(당연히 전 가방보다 크다)에 들어갈 수 있게 된다. 그래서 10가방에는 65보석이 들어갈 수 있게 된다.

 

이러한 이유로 우선순위 큐를 쓰는 것이다.

 

---

코드

package Greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K;
    static Value jew[];
    static int bagInfo[];
 
    static PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2)->{
        return o2 - o1;
    });
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
 
        jew = new Value[N];
        bagInfo = new int[K];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int wei = atoi(st.nextToken());
            int val = atoi(st.nextToken());
            jew[i] = new Value(wei, val);
        }
 
        for (int i = 0; i < K; i++) {
            bagInfo[i] = atoi(br.readLine());
        }
 
        Arrays.sort(jew, (o1, o2)->{
            if(o1.wei == o2.wei) return o2.val - o1.val;
            else return o1.wei - o2.wei;
        });
 
        Arrays.sort(bagInfo);
 
        long sum = 0;
        int idx = 0;
        for (int i = 0; i < K; i++) {
 
            while(idx < N && jew[idx].wei <= bagInfo[i]){
                pq.offer(jew[idx].val);
                idx++;
            }
            if(!pq.isEmpty()) sum += pq.poll();
        }
 
        System.out.println(sum);
    }
 
    static class Value{
        int wei, val;
 
        public Value(int wei, int val) {
            this.wei = wei;
            this.val = val;
        }
    }
}