[백준 1202] 보석 도둑

▪︎ 문제

---

백준 1202 문제

▪︎ 알고리즘 설계

---

• 각 가방은 하나의 보석만 담을 수 있음
• 가방 용량 C보다 작거나 같은 무게의 보석만 담을 수 있음
• 선택된 보석의 총 가격의 합을 최대화해야 함

즉, 여러 개의 제한된 자원(가방)에 대해 이익이 최대가 되도록 보석을 배정하는 문제

각 단계의 최적해를 구하는 문제 → 그리디 알고리즘

• 그리디 알고리즘은 주로 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용한다.

▪︎ 코드

---

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

class Main {
    static class Jewel {
        long weight;
        long price;
        Jewel(long w, long p) {
            this.weight = w;
            this.price = p;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken()); // 보석의 총 개수
        int K = Integer.parseInt(st.nextToken()); // 상덕이의 가방 개수

        // 보석 정보 저장
        Jewel[] jewels = new Jewel[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long M = Long.parseLong(st.nextToken()); // 각 보석의 무게
            long V = Long.parseLong(st.nextToken()); // 각 보석의 가격
            jewels[i] = new Jewel(M, V);
        }
        
        // 가방 정보 저장
        long[] bags = new long[K];
        for(int i = 0; i < K; i++) {
            bags[i] = Long.parseLong(br.readLine()); // 각 가방에 보석을 담을 수 있는 최대 무게
        }

        // 1. 보석을 무게 기준으로 오름차순 정렬 -> 현재 가방 용량 이하의 보석만 힙에 추가하기 위해(무게 제한으로 선택 가능한 보석이 결정됨)
        // - 작은 가방 -> 작은 무게 보석부터 순서대로 확인 가능
        // - 한번 확인한 보석은 다음 가방에도 다시 볼 필요 없이 계속 유지 가능
        Arrays.sort(jewels, (a, b) -> Long.compare(a.weight, b.weight));
        
        // 2. 가방도 무게 기준으로 오름차순 정렬
        Arrays.sort(bags);

        // 최대 힙 (가격 기준) -> 우리는 보석 중 가장 가격이 비싼 것을 빠르게 꺼내야 함!
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 우선순위가 높은 것 먼저 나오는 큐(기본이 최소 힙이기 때문에 Collections.reverseOrder()로 우선순위 반대로 변경!)

        long totalPrice = 0;
        int jewelIndex = 0;

        // 3. 가방 순회
        for (long bacCapacity : bags) {
            // 현재 가방이 수용할 수 있는 보석들을 힙에 추가
            while (jewelIndex < N && jewels[jewelIndex].weight <= bacCapacity) {
                maxHeap.offer(jewels[jewelIndex].price); // 우선순위 큐에 추가
                jewelIndex++;
            }

            // 4. 힙에서 가장 비싼 보석 선택
            if (!maxHeap.isEmpty()) {
                totalPrice += maxHeap.poll();
            }
        }

        System.out.println(totalPrice);
    }
}

• 예시 입력
  • 보석 개수 N = 3, 가방 개수 K = 2
  • 보석 (무게, 가격) : (1, 65), (5, 23), (2, 99)
  • 가방 용량: 2, 10
• 사전 단계
  • 보석을 무게 오름차순으로 정렬:
    • jewels [ (1,65), (2,99), (5,23) ]
  • 가방 오름차순 정렬:
    • bags [ 2, 10 ]
  • 힙 초기 상태:
    • maxHeap = []
    • jewelIndex = 0
    • totalPrice = 0
• 첫 번째 가방 (가방용량 = 2)
  • while문
    • jewelIndex = 0 && jewels[0].weight = 1
      • maxHeap.offer(65) → 힙: [ 65 ]
      • jewelIndex=1
    • jewelIndex = 1 && jewels[1].weight = 2
      • maxHeap.offer(99) → 힙: [ 99, 65 ]
      • jewelIndex=2
    • jewelIndex=2 && jewels[2].weight = 5 → 조건 만족 ❌
  • poll 단계
    • 힙에서 poll() → 99 제거 → 힙: [ 65 ]
    • totalPrice = 99
• 두 번째 가방 (가방용량 = 10)
  • while문
    • jewelIndex=2 && jewels[2].weight = 5
      • maxHeap.offer(23) → 힙 : [ 65, 23 ]
      • jewelIndex=3
    • jewelIndex=3 → 조건 만족 ❌
  • poll 단계
    • 힙에서 poll() → 65 제거 → 힙: [ 23 ]
    • totalPrice = 99 + 65 = 164

▪︎ 시간 복잡도

---

O((N+K)logN)

▪︎ 틀린 이유

---

• 보석은 한 번만 사용가능
  • 각 가방의 선택이 다른 가방에도 영향을 미침
• 가방의 순서가 최적해에 중요할까?
  • 이론적으로 순서는 중요하지 않지만, 구현에서 무게 기준 오름차순으로 처리하지 않으면 후보 보석 집합 관리가 복잡해질 수 있음.
• 초기에, while(C > 0) { ... }와 같은 형태로 while문을 작성했음.
  • C는 한 가방의 용량이 아니라 여러 가방이므로, 이건 잘못된 흐름이였음.
• 보석과 가방을 각각 무게 오름차순으로 정렬하지 않으면 후보 집합을 올바르게 관리할 수 없음.
  • 정렬을 왜 해야하는지에 대한 이해를 못했음.
• 가격이 아니라 무게 기준으로 정렬해야 하는데, 초기에는 왜 무게 기준인지 명확히 이해하지 못한 상태였음.
• 우선순위 큐 생각 못함.

▪︎ 느낀점 / 기억할 정보

---

• 우선순위 큐 사용 이유
  • 항상 가장 비싼 보석을 빠르게 선택하기 위해
• 보석을 가격 기준으로 정렬 → 비효율적 (시간 초과)
• poll() 대신 peek() 사용 → 같은 보석을 여러 번 사용 (오답)
• 가방을 큰 것부터 처리하면서 후보 관리 실수 → 중복 선택이 가능함
• 그리디 알고리즘
  • 각 단계에서 최선(가장 비싼 보석)을 선택해도 전체 최적해가 보장될 때
  • 후보 집합이 단조롭게 확장되도록 관리 → 작은 가방부터 순회하면 로직 단순화 (중복 관리 불필요!)