[ 백준 ] 1202번: 보석도둑

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

문제의 설명은 다음과 같습니다.

• 보석이 총 N개 있다.
• 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.
• 가방은 K개 가지고 있다.
• 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

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

ex
Mi=[1,5,2] vi=[65,23,99],ci=[10,2] 일때
첫번째 보석과 세번째 보석을 선택하면 164 가격을 얻을 수 있다.

알고리즘

• 만약 가방이 버틸 수 있는 무게가 1이라면 고를 수 있는 보석은 무게가 1인 보석중 제일 비싼 보석이다.
• 그렇다면 무게가 N이라면 고를 수 있는 보석은 무게가 1~N까지 중 제일 비싼 보석이다.
• 따라서 버틸 수 있는 무게가 낮은 가방부터 고를수 있는 후보에서 제일 비싼 보석을 고르면 된다.
• 자료구조
  • <가격,보석값어치>를 저장하는 hash map
  • 보석 가격을 저장하는 우선순위 큐(Max heapq)
  • 우선순위 큐에 현재까지 넣은 보석의 가격 리스트의 인덱스를 저장하는 포인터 => curPointer=0
• 1. 가방이 버틸 수 있는 무게 i에 대해
• 2. curPointer 부터 무게 i보다 같거나 작은 보석들을 우선순위 큐에 넣는다.
• 3. curPointer를 업데이트 한다.
• 4. 가장 비싼 보석을 고른다.

배운점

• 이 문제 역시 1209번과 같이 우선순위 큐를 사용했다.
  그 이유는 고를수 있는 후보들이 특정 시점에 추가되는 공통점이 있다.

코드 python

from collections import defaultdict
import sys
import heapq

n,k=map(int,input().split())
diamond=defaultdict(list)
for i in range(n):
    weight,price=map(int,sys.stdin.readline().rstrip().split())
    diamond[weight].append(price)
bag=sorted([ int(sys.stdin.readline().rstrip())  for _ in range(k)])
weightKey=sorted(diamond.keys())
curPush=0
pq=[]
answer=0
for i in bag:
    while curPush<len(weightKey) and weightKey[curPush]<=i:
        for k in diamond[weightKey[curPush]]:
            heapq.heappush(pq,(-k,k))
        curPush+=1
    if pq:
        answer+=heapq.heappop(pq)[1]
print(answer)