1202: 보석 도둑

문제 링크

1202: 보석 도둑

구현 방식

• 가방에는 최대 한 개의 보석만 넣을 수 있음
• jewels를 (무게, 가격) 형식으로 오름차순 정렬 (최소힙 이용)
• bags를 담을 수 있는 최대 무게 기준으로 오름차순 정렬
  • 하나의 가방에는 최대 한 개의 보석만 넣을 수 있기 때문에 용량이 작은 가방부터 채워나가야함
• bags를 기준으로 순회
  • candi를 최대힙으로 설정하여 각 가방마다 while문을 돌면서 가장 가격이 비싼 보석을 선정

코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().strip().split())
jewels = []
for n in range(N): heapq.heappush(jewels, list(map(int, sys.stdin.readline().strip().split())))
bags = []
for k in range(K): bags.append(int(sys.stdin.readline().strip()))
bags.sort()

answer = 0
candi = []
for bag in bags: #가방을 순회
    while jewels and bag >= jewels[0][0]:
        heapq.heappush(candi, -jewels[0][1]) #가격에 대해 최대힙
        heapq.heappop(jewels)
    if candi: answer -= heapq.heappop(candi)
print(answer)