[ BOJ ][JAVA][1202] 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	17513	4009	2816	22.286%

문제

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

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

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

출력

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

예제 입력 1

3 2
1 65
5 23
2 99
10
2

예제 출력 1

164

코드

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

public class p1202 {
    static class Pair implements Comparable<Pair>{
        int w, c;
        public Pair (int w, int c) {
            this.w = w;
            this.c = c;
        }

        public int compareTo(Pair o) {
            return w - o.w;
        }
    }
    static int n, k;
    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());
        PriorityQueue<Pair> jew = new PriorityQueue<>();
        PriorityQueue<Integer> bag = new PriorityQueue<>();
        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            jew.offer(new Pair(w, c));
        }

        while (k-- > 0) {
            bag.offer(Integer.parseInt(br.readLine()));
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long ans = 0;
        while (!bag.isEmpty()) {
            int bagSize = bag.poll();
            while (!jew.isEmpty()) {
                Pair cur = jew.poll();
                // 꺼낸 보석의 무게가 가방의 무게를 초과한다면 보석을 다시 집어 넣고 다음 보석을 탐색한다.
                if (cur.w > bagSize) {
                    jew.offer(cur);
                    break;
                } else {
                    // 나중에 오름차순으로 빼기 위해서 -1을 곱하고 넣어준다.
                    pq.offer(cur.c * -1);
                }
            }
            if (!pq.isEmpty()) {
                ans += pq.poll();
            }
        }

        System.out.println(ans * -1);
    }
}