[그리디] 코딩테스트 문제 TIL (보석 도둑) - 백준 1202번

말하는 감자·2024년 12월 19일

TIL baekjoon greedy heap priority queue python sorting 그리디 백준 우선순위 큐 정렬 코딩테스트 코딩테스트 준비 파이썬 힙

코딩테스트 유형별 풀이

목록 보기

40/67

1. 오늘의 학습 키워드

그리디
우선순위 큐
정렬
힙

2. 문제: 1202. 보석 도둑

단계: 🥇 골드 2단계
주제:
출처: https://www.acmicpc.net/problem/1202

문제

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

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

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

출력

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

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

3. 문제 풀이

Step1. 문제 이해하기

보석이 총 N개가 있습니다. 각 보석은 무게 $M_i$ 와 가격 $V_i$ 로 정의됩니다.
도둑은 가방 K개를 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 $C_i$ 입니다.
그리고 가방에는 최대 1개의 보석만 넣을 수 있습니다.

목표: 각 가방에 보석을 최대한 담아 훔칠 수 있는 최대 가격을 계산합니다.

입출력을 살펴보도록 하겠습니다.

Input:
- 첫째 줄에 N과 K가 주어집니다. N과 K는 1이상 $3 * 10^5$ 이하입니다.
- 다음 N개 줄에는 각 보석의 정보 무게와 가격이 주어집니다.
- 다음 K개의 줄에는 가방에 담을 수 있는 최대 무게가 주어집니다.
Output:
- 도둑이 훔칠 수 있는 보석 가격의 합의 최댓값을 출력합니다.

Step2. 문제 분석하기

일단 보석은 쪼갤수가 없습니다. 그렇다면 각 가방에 보석을 최대한 담을려면 가방의 크기가 작은(여기서 크기가 작다는 것은 수용할 수 있는 무게가 작은것을 말합니다.) 가방에 무게가 작은 보석을 담으면 보석 가격의 합이 최대가 될 수 있습니다.

즉, 보석은 무게 기준으로 오름차순으로 정렬, 가방은 용량 기준 오름차순으로 정렬합니다.

보석: 무게가 가벼운 보석부터 가방에 넣기 위해 정렬
가방: 작은 용량의 가방부터 채우기 시작해야 효율적임

그리고 또 명심해야 할 점은 각 가방에는 보석을 1개 담을수 있습니다.

그렇기 때문에 현재 가방에 담을 수 있는 보석들 중에서 가격이 가장 높은 보석 1개를 선택해야 합니다. 따라서 최대 힙 자료구조를 활용하는 우선 순위큐를 사용해야 합니다.

따라서, 가방의 용량이 작은순으로 가방을 순회하면서, 현재 가방에 담을 수 있는 모든 보석을 우선순위 큐에 추가합니다.

큐에서 가장 높은 가격의 보석을 꺼내 가방에 담습니다.

Step3. 코드 설계

Step4. 코드 구현

import sys
from heapq import heappop, heappush

N, K = map(int, sys.stdin.readline().split())
jewels = [[*map(int, sys.stdin.readline().split())] for _ in range(N)]
bags = [int(sys.stdin.readline().strip()) for _ in range(K)]

jewels.sort()
bags.sort()
heap = []
idx = 0
max_price = 0
for bag in bags:
    
    while idx < N  and jewels[idx][0] <= bag:
        heappush(heap,(-jewels[idx][1]))
        idx += 1
    
    if heap:
        max_price -= heappop(heap)
print(max_price)

코드 설명:
1. 입력 처리 및 정렬:
  - 보석과 가방을 각각 jewels와 bags에 저장하고 정렬합니다.
  - jewels는 무게 기준으로, bags는 용량 기준으로 오름차순 정렬합니다.
2. 우선순위 큐 활용:
  - heap을 이용하여 현재 가방에 담을 수 있는 모든 보석을 저장합니다.
  - jewels[idx][1]를 삽입하여 최대 힙처럼 동작하도록 구현합니다.
3. 가방 순회 및 가격 계산:
  - 각 가방에서 담을 수 있는 보석들을 모두 큐에 넣은 후, 가격이 가장 높은 보석을 선택하여 누적합니다.
시간 복잡도:
1. 정렬:
  - 보석 정렬: $O(N \log N)$
  - 가방 정렬: $O(K \log K)$
2. 가방 순회:
  - 각 가방에 대해 보석을 확인하며 힙 연산을 수행:
  - 보석 확인: $O(N)$
  - 힙 삽입 및 제거: $O(\log N)$
  
  최종 시간 복잡도는 $O(N \log N + K \log K)$ 입니다.
결과:

4. 마무리

이 문제는 정렬과 우선순위 큐를 활용하여 최적의 선택을 반복적으로 수행하는 그리디 알고리즘의 대표적인 예입니다. 보석과 가방을 각각 정렬하여 작은 크기부터 처리하며, 우선순위 큐를 통해 가장 비싼 보석을 선택하는 방식이 핵심입니다. 이 접근법을 통해 $O(N \log N + K \log K)$ 의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.