[BOJ][Java] 백준 1202번: 보석 도둑

문제 설명

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

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

문제 풀이

이 문제는 그리디와 우선순위 큐를 사용하여 해결하는 문제입니다. 핵심은 가방에 1개의 보석만 넣을 수 있다는 점에 초점을 맞춰서 무게에 따라 보석을 넣어주면 됩니다.

 

1. 보석을 무게에 대해 오름차순으로 정렬하되, 무게가 같은 경우 가격에 대해 내림차순으로 정렬한다.

2. 가방은 무게를 기준으로 오름차순으로 정렬한다.

3. 모든 가방에 대해 반복문을 돌되 우선순위 큐에 그 가방보다 무게가 작은 보석들을 넣어준다.

4. 우선순위 큐가 비어있지 않은 경우 제일 앞의 보석 (가치가 높은 보석)을 꺼내서 더해준다.

 

저도 처음에는 모든 보석을 우선순위 큐에 집어넣고 보석을 하나씩 비교하며 해당 가방의 위치를 이분탐색을 통해 찾아보자는 생각으로 구현했지만 시간초과가 떴습니다. 따라서 이분탐색 및 가방의 위치를 찾는 것보다 가방의 무게를 기준으로 탐색을 하는 것이 더 빠른 해결법이었습니다

풀이 코드

import java.io.*;
import java.util.*;

public class Main {

    private static int N, K;
    private static Gem[] gems;
    private static int[] bags;
    private static boolean[] isFull;

    public static void main(String[] args) throws IOException {
        input();
        process();
    }

    private static void process() {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        long ans = 0;
        for (int i = 0, j = 0; i < K; i++) {
            while (j < N && gems[j].weight <= bags[i]) {
                pq.offer(gems[j++].value);
            }

            if (!pq.isEmpty()) {
                ans += pq.poll();
            }
        }

        System.out.println(ans);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        gems = new Gem[N];

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            gems[i] = new Gem(M, V);
        }

        Arrays.sort(gems, (g1, g2) -> {
            if (g1.weight == g2.weight) return g2.value - g1.value;
            return g1.weight - g2.weight;
        });

        bags = new int[K];
        for (int i=0; i<K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bags);
    }

    static class Gem{
        int weight, value;

        public Gem(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
}

 

 

<출처>

1202번: 보석 도둑