[백준] 1202 보석 도둑 (JAVA)

문제 링크:

1202번: 보석 도둑

 

 

난이도: 골드2

 

 

문제:

 

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

 

상덕이가 털 보석점에는 보석이 총 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)

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

 

 

출력:

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

문제 이해:

이 문제는 첫줄에 N과 K가 주어진다 여기서 N은 보석 개수 K는 가방 개수이다.

그 이후에 보석 개수만큼 무게와 가치가 입력되며 가방 개수만큼 무게가 입력된다.

 

예제 입력 2를 예시로 들어보면 

3 2
1 65
5 23
2 99
10
2

보석 3개 가방 2개가 입력 됐으며,

보석 1: 무게1, 가치 65

보석 2: 무게 5, 가치 23

보석 3: 무게 2, 가치 99

가방 1: 무게 10

가방2: 무게 2 형식으로 입력된 것이다.

 

가방에는 최대 한개 보석만 담을 수 있으며  훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

예제 입력 2를 보면 무게가 2인 가방에 99 가치인 보석을 담을 수 있고 무게가 10인 가방에 65 가치인 보석을 담을 수 있어

최종 결과는 164가 된다.

 

 

구현 방향:

이 문제는 처음 보자마자 그리디 알고리즘과 우선순위 큐(Priority Queue) 가 떠올랐다.

 

보석의 가치(value) 를 우선순위로 설정하여, 가장 가치가 높은 보석이 먼저 나오도록 우선순위 큐를 구성한다.

이후 큐가 빌 때까지 보석을 하나씩 꺼내면서, 현재 가방에 담을 수 있는 경우에만 담는 방식으로 정답을 구한다.

 

단, 주의할 점이 있다.
보석의 가치는 최대 1,000,000, 가방의 개수는 최대 300,000이므로,
결과의 합이 int형 범위를 초과할 수 있다.
따라서 결과값은 반드시 long형으로 계산해야 한다.

 

이를 코드로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int N, K;
    static TreeMap<Integer, Integer> bagMap = new TreeMap<>();

    static Queue<double[]> q = new PriorityQueue<>(
            (a, b) -> {
                if (a[1] == b[1]) return Double.compare(a[0], b[0]);
                return Double.compare(b[1], a[1]);
            }
    );

    public static long solve() {
        long result = 0L;
        while (!q.isEmpty()) {
            double[] arr = q.poll();
            long m = (long) arr[0];
            long v = (long) arr[1];

            // 현재 무게 m 이상 중 가장 작은 가방 찾기
            Integer bag = bagMap.ceilingKey((int) m);

            if (bag != null) {
                result += v;
                // 가방 하나 사용 처리
                if (bagMap.get(bag) == 1) bagMap.remove(bag);
                else bagMap.put(bag, bagMap.get(bag) - 1);
            }
        }
        return result;
    }

    public static void main(String[] args) 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());

        // 보석 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long m = Long.parseLong(st.nextToken());
            long v = Long.parseLong(st.nextToken());
            q.add(new double[]{m, v});
        }

        // 가방 입력
        for (int i = 0; i < K; i++) {
            int c = Integer.parseInt(br.readLine());
            bagMap.put(c, bagMap.getOrDefault(c, 0) + 1); // 같은 무게 가방 처리
        }

        long result = solve();
        System.out.println(result);
    }
}

 

 

마무리 하며:

이 문제는 골드 2 수준으로 난이도가 높은 편이기에, 분명 내가 고려하지 못한 요소가 있을 것이라 예상했다.

 

그러나 작성자는 처음에 가방을 리스트(List) 에 담아 remove(bag) 연산을 수행하면서,
리스트가 순차 탐색(O(N)) 으로 동작해 시간 복잡도가 커져 시간 초과가 발생하는 문제를 겪었다.
또한, 결과값을 int형으로 처리해 값의 범위를 초과(long 미사용) 하는 실수로 인해 수십 번의 오답을 냈다.

 

결국 AI의 도움을 받아 TreeMap을 사용했고,
TreeMap이 내부적으로 이진 탐색 트리(Red-Black Tree) 로 구현되어 있어
연산 복잡도를 O(log N) 으로 줄일 수 있었고, 그 결과 문제를 해결할 수 있었다.

 

사실 구현 자체는 어렵지 않았지만,
이러한 최적화 요소를 간과해 틀렸다는 점에서 개인적으로는 “좋은 문제”라 느껴지진 않았다.

 

그러나 동시에, 어떤 상황에서 어떤 자료구조를 선택해야 시간 복잡도를 줄일 수 있는지 깨닫게 되었고,
이런 부분까지 고려하는 것이 진정한 실력이라 생각하게 되었다.

 

 

감사합니다.