[백준 1202] 보석 도둑 - JAVA

BOJ Link

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

 

 

풀이 과정

우선순위 큐를 2개 사용한다.

보석을 무게 기준 오름차순 정렬한다. 가방을 무게 기준 오름차순으로 우선순위 큐(kq)에 넣는다.

 

(kq)에서 무게가 작은 가방부터 탐색하며, 다음 과정을 반복한다.

 

1. 현재 보석을 가방에 담을 수 있다면, 우선순위 큐(vq)에 보석의 가치를 내림차순으로 저장한다.

해당 보석을 vq에 넣었으므로, 다음 가방에서 보석을 넣을 수 있는지를 탐색할 시작점인 idx를 올린다.

 

2. 담을 수 없다면, 뒤의 보석들도 담을 수 없으므로 탐색을 종료한다.

 

3-1. vq에는 현재 가방으로 낼 수 있는 가치가 내림차순으로 정렬되어있다. peek값을 ans에 누적하고 가방과 보석을 사용 처리한다.

3-2. 만약 vq가 비어있다면, 현재 가방엔 넣을 수 있는 보석이 없다. 다음 가방으로 넘어간다.

(애초에 넣을 수 있는 보석이 없거나, 그리디하게 더 무게가 작은 가방에 넣었고 현재 가방으론 넣을 보석이 없는 상태이다.)

 

문제의 조건에 따라,

답은 Integer.MAX_VALUE를 넘어갈 수 있으므로 ans를 long으로 선언한다.

가방이 남을수도, 가방보다 넣을 수 있는 보석이 더 많을수도 있으므로 !kq.isEmpty() && k < K를 탐색의 조건으로 한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    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());

        List<int[]> list = new ArrayList<>();

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

        Collections.sort(list, Comparator.comparingInt(o -> o[0]));

        PriorityQueue<Integer> kq = new PriorityQueue<>();

        for (int i = 0; i < K; i++) {
            kq.offer(Integer.parseInt(br.readLine()));
        }

        long ans = 0;
        int k = 0;

        PriorityQueue<Integer> vq = new PriorityQueue<>(Comparator.reverseOrder());
        int idx = 0;

        while (!kq.isEmpty() && k < K) {


            for (int i = idx; i < list.size(); i++) {

                int[] now = list.get(i);
                if (now[0] > kq.peek()) break;

                vq.offer(now[1]);
                idx++;
            }

            if (vq.isEmpty()) {
                kq.poll();
                continue;
            }

            k++;
            ans += vq.poll();
            kq.poll();
        }

        System.out.println(ans);
    }
}