[🥇2 / 백준 1202 / 파이썬] 보석 도둑

 

1202번: 보석 도둑

 

문제

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

상덕이가 털 보석점에는 보석이 총 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 1 5 10 100 100 11	예제 출력 1  10
예제 입력 2  3 2 1 65 5 23 2 99 10 2	예제 출력 2  164

 

풀이

 

각 가방에 담을 수 있는 최대 무게를 벗어나지 않고, 최대 가치의 보석을 담아야 하는 문제이다.

정렬과 우선순위 큐를 적절히 사용해야 한다.

 

생각보다 어려웠던 문제였다.

포인트는 가방을 오름차순 정렬했을 때, 앞에 가방에 넣을 수 있는 모든 보석은 뒤의 가방에도 넣을 수 있다는 것이다.

 

보석 리스트는 스택처럼 사용한다. 작은 것부터 pop할 것이므로 내림차순 정렬한다.

우선순위 큐는 최대 힙을 이용하여, 보석의 무게 중 가장 가치가 큰 것을 앞에 오도록 한다.

파이썬의 경우 heapq 모듈의 기본 설정은 최소 힙이므로, 가치에 음수를 곱하여 최대 힙처럼 사용한다.

 

최대 힙에는 현재 순환중인 가방에 담을 수 있는 보석들이 담겨질 것이다.

위에서 언급했듯, 이 최대 힙은 다음 가방을 순환할 때에도 유지되어 목록이 전승된다.

 

import sys, heapq
input = sys.stdin.readline

n,k = map(int,input().split())
# 보석은 무게가 작은 것부터 pop할 것이므로 내림차순 정렬
jewel = [tuple(map(int,input().split())) for _ in range(n)]
jewel.sort(reverse = True)
back = [int(input()) for _ in range(k)]
back.sort()

ans,hq = 0,[]
for b in back:
    # 보석을 순회하며 현재 가방에 담을 수 있는 것들을 heap에 담는다.
    while jewel:
        w,v = jewel.pop()
        if w > b:
            jewel.append((w,v))
            break
        heapq.heappush(hq,(-v,w))
        
    # 이제 보석이 더 이상 없거나 현재 가방의 최대 무게보다 무거움.
    # 따라서 현재 가방에 담을 수 있는 것 중 가장 가치가 높은 것을 꺼낸다.
    if hq:
        v,w = heapq.heappop(hq)
        if w > b:
            heapq.heappush(hq,(v,w))
            continue
        ans += v
        
print(-ans)