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

문제

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

상덕이가 털 보석점에는 보석이 총 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. 보석을 arraylist로 입력받은 후 무게 순서대로 오름차순 정렬한다.
2. 가방에 담을 수 있는 최대 무게를 입력 받은 후 오름차순 정렬한다.
3. 가격 순서대로 내림차순 정렬을 하는 우선순위 큐를 생성한다.
4. 현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담아준다.
5. 우선순위 큐의 제일 첫 번째 값(가장 가격이 비싼 보석)을 꺼내어 더해준다.
6. 4 ~ 5를 반복해주면 된다.

풀이

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

class Gem {

    int m;
    int v;

    Gem(int m, int v) {
        this.m = m;
        this.v = v;
    }
}

public class prob1202 {

    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());
        ArrayList<Gem> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list.add(new Gem(m, v));
        }
        Collections.sort(list, ((o1, o2) -> o1.m - o2.m)); //무게 순서대로 오름차순 정렬
        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine()); //배낭 무게 입력
        }
        Arrays.sort(bags); //배낭 무게 오름차순 정렬

        PriorityQueue<Gem> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v); //가격 순서대로 내림차순 정렬
        long total = 0;
        int idx = 0;
        for (int i = 0; i < K; i++) {
            //현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담아준다.
            while (idx < N && list.get(idx).m <= bags[i]) {
                Gem current = list.get(idx++);
                pq.add(new Gem(current.m, current.v));
            }
            // 우선순위 큐에 있는 요소를 하나 빼서 가방에 넣음.
            // 이 때, 우선순위 큐는 내림차순 정렬이 되어있으므로
            // 첫 번째 요소는 가장 가격이 비싼 보석을 의미함.
            if (!pq.isEmpty()) {
                total += pq.poll().v;
            }
        }
        System.out.println(total);
        br.close();
    }

}