[JAVA] 1202 보석 도둑

난이도

골드2

 

코드

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

public class Main {
    private static Comparator<long[]> comparator = new Comparator<long[]>() {
        @Override
        public int compare(long[] x, long[] y) {
            if(x[1] != y[1]) {
                return (int)(y[1] - x[1]);
            } else {
                return (int)(y[0] - x[0]);
            }
        }
    };

    // 실행 시간 단축
    // : jewels & bags가 무게 오름차순으로 정렬이므로
    //   다음 bag에 들어갈 수 있는 candidates에는 이전 bag의 candidates가 포함됨
    //   따라서 굳이 candidates에 들어간 jewel들을 뺄 필요가 없다
    private static PriorityQueue<long[]> candidates = new PriorityQueue<>(comparator);

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int K = Integer.parseInt(stringTokenizer.nextToken());
        
        PriorityQueue<long[]> jewels = new PriorityQueue<long[]>(
            new Comparator<long[]>() {
                // jewels: 무게 오름차순 -> 가격 내림차순으로 정렬
                @Override
                public int compare(long[] x, long[] y) {
                    if(x[0] != y[0]) {
                        return (int)(x[0] - y[0]);
                    } else {
                        return (int)(y[1] - x[1]);
                    }
                }
            }
        );

        for(int i = 0; i < N; i++) {
            jewels.add(Arrays.stream(bufferedReader.readLine().split(" "))
                        .mapToLong(Long::valueOf).toArray());
        }

        List<Long> bags = new ArrayList<>();
        for(int i = 0; i < K; i++) {
            bags.add(Long.valueOf(bufferedReader.readLine()));
        }

        // bags: 무게 순으로 오름차순 정렬
        bags.sort(Comparator.naturalOrder());

        long dp[] = new long[K];
        // dp[bag]: 0, ..., bag 가방들에 보석을 담을 때 최대 가격
        // dp[bag] = dp[bag - 1] + (bag 가방에 담는 최대 가격)
        
        dp[0] = calculateCurrentDP(jewels, bags, 0);
        int index = 1;
        for(; index < K; index++) {
            // bag 가방에 담는 최대 가격
            // : 남은 보석들 중 bag 가방 무게 이내의 보석들이 후보
            //   그 중 최고가의 보석 선택
            dp[index] = dp[index - 1] + calculateCurrentDP(jewels, bags, index);
        }

        System.out.println(dp[index - 1]);
    }

    private static long calculateCurrentDP(PriorityQueue<long[]> jewels, List<Long> bags, int index) {
        while(!jewels.isEmpty() && jewels.peek()[0] <= bags.get(index)) {
            candidates.add(jewels.poll());
        }

        return !candidates.isEmpty() ? candidates.poll()[1] : 0;
    }
}

 

알고리즘

DP

1. 보석들을 무게가 무거운 순으로 정렬한다.
2. 가방들을 보석을 담을 수 있는 최대 무게가 가벼운 순으로 정렬한다.
3. 정렬된 가방을 차례대로 탐색한다.
   3-1. 현재 가방에 들어갈 수 있는 보석들을 후보에 추가한다.
   3-2. 후보들 중 가장 가격이 높은 보석을 현재 가방에 담는다.

비고

보석들은 가격이 아닌 무게 순으로 정렬한다.

: 최대 가격을 구하는 것이 목표이지만, 아무리 가격이 높아도 무게 때문에 가방에 넣을 수 없는 경우가 발생한다. 무게 제한에 걸리는 보석을 먼저 필터링한 후에 가격을 고려한다.

 

이전 결과를 활용해 연산 시간을 줄인다.

: 가방들을 보석을 담을 수 있는 최대 무게가 가벼운 순으로 정렬한 이유는, 이전 가방에 담지 않았던 후보들을 현재 가방에서 활용하기 위함이다. 이전 가방에 담을 수 있는 보석이라면 그보다 무거운 보석을 담을 수 있는 현재 가방에도 담을 수 있다.

 

숫자는 오버플로우를 조심한다.

: 당연하지만 입력값이 작아도 연산의 결과값은 클 수 있다. 입력값은 물론이고 결과값의 자료형에 주의한다.