[백준] 1202번 보석 도둑 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘

---

---

---

💡 문제

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

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

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 M$_i$와 V$_i$가 주어진다. (0 ≤ M$_i$, V$_i$ ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 C$_i$가 주어진다. (1 ≤ C$_i$ ≤ 100,000,000)

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

출력

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

---

💭 접근

주어진 가방을 사용하여 훔칠 수 있는 보석의 최대 가치를 구하기 위해선,

1. 먼저 보석과 가방을 무게 기준으로 오름차순 정렬한다.
2. 이후 가장 용량이 적은 가방부터 이 가방보다 가벼운 보석을 모두 고른다.
3. 만약 현재 가방보다 가벼운 보석이 있다면 이중 가장 가치가 높은 보석을 훔친다.

우선순위 큐를 사용하면 위 방법을 쉽게 구현할 수 있으며, 우선순위 큐의 heapq.heappop()의 경우 가장 작은 수 부터 꺼내므로 보석의 가치에 -부호를 붙여 리스트에 저장하면 가장 가치가 높은 보석을 우선적으로 꺼낼 수 있다.

---

📒 코드

import sys
import heapq
# input = sys.stdin.readline

n, k = map(int, input().split())
jewels = [list(map(int, input().split())) for _ in range(n)]
bags = [int(input()) for _ in range(k)]
jewels.sort()
bags.sort()

ans = 0
tmp = []
for bag in bags: # 용량이 작은 가방부터
	# 그 가방보다 가벼운 보석은 모두 리스트에 담는다.
    while jewels and jewels[0][0] <= bag: 
        heapq.heappush(tmp, -jewels[0][1])
        heapq.heappop(jewels)
    if tmp: # 용량보다 가벼운 보석이 있다면 가장 가치가 높은 보석을 훔친다.
        ans -= heapq.heappop(tmp)
print(ans)

---

💭 후기

그리디 문제는 풀고나면 별거 아닌 것 같지만 이런 방법을 떠올리고, 이러한 방법이 타당한지 여부를 판단하는 것이 매우 까다로운 것 같다.

---

🔗 문제 출처

https://www.acmicpc.net/problem/1202

---