P.1202 보석 도둑

코드

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    static public class Jewel implements Comparable{
        int weigh;
        int price;

        public Jewel(int weigh, int price) {
            this.weigh = weigh;
            this.price = price;
        }

        @Override
        public int compareTo(Object o) {
            Jewel jewel = (Jewel) o;

            if (this.weigh != jewel.weigh) return (this.weigh - jewel.weigh);
            else return -(this.price - jewel.price);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = line[0], k = line[1];
        Jewel[] jewels = new Jewel[n];
        for (int i = 0; i < n; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            jewels[i] = new Jewel(line[0], line[1]);
        }
        Arrays.sort(jewels);
        Integer[] bags = new Integer[k];
        for (int i = 0; i < k; i++) bags[i] = Integer.parseInt(br.readLine());
        Arrays.sort(bags);

        PriorityQueue<Jewel> queue = new PriorityQueue<>(Comparator.comparing(o -> -o.price));
        int idx = 0;
        long ans = 0;
        for (Integer bag : bags) {
            while (idx < n && jewels[idx].weigh <= bag) queue.add(jewels[idx++]);

            if (!queue.isEmpty()) ans += queue.poll().price;
        }

        bw.write(Long.toString(ans));
        bw.flush();
    }
}

코드 설명

N과 K가 각각 300,000이므로 O(N * K)안엔 해결하지 못한다.

O(N * logK) 혹은 O(K * logN)안에 해결해야한다.

 

상덕이가 최대 가격을 훔칠 수 있기 위해서는 모든 가방을 사용하는 것이 유리하다.

최대 가격을 훔칠 수 있는 조건은 다음과 같다.

1. 모든 가방에 보석을 담아야 한다.
2. 한 가방에 최대한 이득을 볼 수 있는 보석을 담는다.

한 가방에 최대한 이득을 보기 위해서는 이 가방에 필요한 무게보다 작으면서 가장 높은 가격을 가진 보석을 넣어야 한다.

 

무게를 기준으로 가방과 보석을 정렬할 경우 각 가방이 담을 수 있는 무게의 범위는 다음과 같다.

bag[0]에 담을 수 있는 보석은 bag[1]이 담을 수 있고, bag[1]에 담을 수 있는 보석은 bag[2]에 담을 수 있다.

따라서 우선순위 큐를 두고 bag[0]에 담을 수 있는 보석을 모두 담아둔 후 가치가 가장 높은 보석을 bag[0]에 담으면 된다.

bag[1]에 담을 수 있는 보석에는 bag[0]에 담을 수 있는 보석이 포함되므로 이전에 사용한 우선순위 큐를 계속해서 사용할 수 있다.