[백준]:1202: 보석 도둑(java)

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

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

2 1
5 10
100 100
11

예제 출력 1

10

---

풀이

1. 보석과 가방을 무게를 기준으로 오름차순으로 정렬해준다.

Collectoins.sort 사용한 이유는 더 빨라서 사용했습니다.

2. 현재 넣으려는 가방(가방중에 가장 가벼운 무게를 넣을 수 있는) 에 넣을 수 있는 보석을 모두 우선순위큐에 담는다.

- 현재 내 가방의 무게보다 더 작은 무게의 보석이 모두 우선순위 큐에 들어간다.

3. 우선순위큐는 내림차순으로 무게로 정렬이 되며 하나를 뽑아주면 가장 무거운게 나온다.

- 현재 내 가방에 가장 큰 보석을 넣는 과정.

4. 2번 과정을 반복하는데 이미 우선순위큐에 들어가있는것도 누적 돼 확인하게된다.

전체 코드

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

public class BJ_G2_1202_보석도둑 {
    static class Jewel implements Comparable<Jewel>{
        int m;
        int v;
        Jewel(int m, int v) {
            this.m = m;
            this.v = v;
        }

        @Override
        public int compareTo(Jewel o) {
            return this.m-o.m;
        }
    }

    static class Num implements Comparable<Num> {
        int n;
        Num(int n) {
            this.n = n;
        }

        @Override
        public int compareTo(Num o) {
            return o.n - this.n;
        }
    }
    public static void main(String[] args) throws Exception {
        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<Jewel> jewel = 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());
            jewel.add(new Jewel(m, v));
        }
        ArrayList<Integer> bag = new ArrayList<>();
        for(int i=0; i<K; i++) {
            bag.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(jewel);
        Collections.sort(bag);

        long sum = 0;
        int idx = 0;
        PriorityQueue<Num> pq = new PriorityQueue<>();

        for(int i=0; i<K; i++) {
            for(int j=idx; j<N; j++) {
                if(jewel.get(j).m <= bag.get(i)) {
                    idx++;
                    pq.add(new Num(jewel.get(j).v));
                } else {
                    break;
                }
            }
            if(pq.isEmpty()) continue;
            sum+=pq.poll().n;
        }
        System.out.println(sum);
    }
}