백준 1202번: 보석 도둑 (파이썬)

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

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)

 

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

 

출력

 

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

 

풀이

 

보석의 무게, 가격을 튜플 형태로 저장한 뒤 오름차순 정렬한다.

가방의 무게도 마찬가지로 오름차순 정렬한다.

이후 가벼운 가방부터, 가방에 넣을 수 있는 모든 보석의 가격 값을 우선순위큐에 저장하고 그 중에서 가장 높은 가격을 가져오면 된다.

 

이때 반드시 오름차순 정렬을 해서 가벼운 가방부터 비교해야만, 이전 단계에서 우선순위큐에 저장된 보석들이 다음 단계에서도 가방에 넣을 수 있는 보석들이 된다.

예를 들어, 다음과 같이 입력된 경우를 생각해 보자.

3 2
1 1
2 3
5 2
5
2

무게가 5인 가방부터 비교하면, 무게가 2인 보석이 이 가방에 들어가고 다른 가방에 무게가 1인 보석이 들어가 총 가격은 4가 된다.

하지만 무게가 2인 가방부터 비교하면, 무게가 2인 보석이 이 가방에 들어가고 다른 가방에 무게가 5인 보석이 들어가 총 가격은 5가 된다.

이렇게 오름차순 정렬을 해서 가벼운 가방부터 비교해야 최적의 결과를 얻을 수 있다.

 

기본적으로 heapq는 오름차순으로 정렬되기 때문에, 저장할 때 -를 붙여줌으로써 내림차순으로 사용할 수 있게 하였다.

 

소스 코드

 

import sys
import heapq

n, k = input().split()
n, k = int(n), int(k)

infos = []
for i in range(n):
    m, v = sys.stdin.readline().split()
    m, v = int(m), int(v)
    infos.append((m, v))
infos.sort()

cs = []
for i in range(k):
    cs.append(int(sys.stdin.readline()))
cs.sort()

available = []
value = 0
for i in range(k):
    while infos and cs[i] >= infos[0][0]:
        heapq.heappush(available, -infos[0][1])
        heapq.heappop(infos)
    
    if available:
        value -= heapq.heappop(available)
print(value)