[BOJ-1202] 보석 도둑(JAVA)

백준 1202 보석 도둑

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 )

 

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

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제에서 중요한 것은, 해당 가방에 넣을 수 있는 보석 중 가장 가치가 큰 것을 넣어야 한다는 것이다.

 

 - 단순하게 생각해보면, 각 무게마다 가능한 경우의 수를 모두 구하면 된다.

 

 - 이 경우 O($N x K$)의 시간복잡도가 된다.

 

 - 이 것을 좀 더 개선하는 방법은, 우선순위 큐를 이용하면 된다.

 

 - 먼저 보석을 무게 순으로 오름차순 정렬한다.

 

 - 그 다음 가방을 무게 순으로 오름차순 정렬한다.

 

 - 가벼운 가방부터 오름차순 정렬된 보석을 해당 가방의 무게보다 커질 때 까지 뽑는다.

 

 - 뽑은 보석들을 우선순위 큐에 넣는다.

 

 - 가방의 무게보다 커질 때 우선순위 큐에 있는 top 보석을 뽑는다.

 

 - 이 과정을 거치면, 보석의 최대값을 얻을 수 있다.

 

 - 이때 시간복잡도는 logN + logK + NlogK 이므로 O(NlogK)가 된다.

 

 

---

 

 

소스 코드

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        List<Node> gems = new ArrayList<>();

        for(int i=0;i<N;i++){
            st = new StringTokenizer(bf.readLine());

            int M = Integer.parseInt(st.nextToken());

            int V = Integer.parseInt(st.nextToken());

            Node node = new Node(M,V);

            gems.add(node);

        }

        List<Integer> bags = new ArrayList<>();

        for(int i=0;i<K;i++){
            bags.add(Integer.parseInt(bf.readLine()));
        }

        Collections.sort(bags);

        Collections.sort(gems);

        int startIndex = 0;

        long result = 0;

        for(int i=0;i<K;i++){
            int bagM = bags.get(i);

            for(;startIndex<N;startIndex++){
                if(gems.get(startIndex).M <= bagM){
                    pq.add(gems.get(startIndex).V);
                }
                else{
                    break;
                }
            }
            if(!pq.isEmpty()){
                result += pq.poll();

            }

        }
        System.out.println(result);
    }

    static class Node implements Comparable<Node> {
        int M;
        int V;

        public Node(int m, int v) {
            M = m;
            V = v;
        }

        @Override
        public int compareTo(Node o) {
            return this.M - o.M;
        }
    }

}