[백준] 1202번: 보석 도둑 (우선순위 큐)

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

1202번: 보석 도둑

 

 

그림판으로 예제에 대한 그림을 한 번 그려보았다.

 

이 문제는 우선순위 큐로 접근해야하는 문제이다.

 

문제 풀이 방법은 다음과 같다.

 

우선 보석들과 가방들의 무게에 따라 리스트를 정렬한다.

임시 temp 리스트를 만들고 가장 무게가 작은 가방부터 순서대로 모든 보석들을 넣어본다.

(단, max_heap 우선순위 큐를 사용하며, 보석의 무게가 가방의 수용 가능 무게보다 작거나 같을 때에만 넣어준다.)

 

각 가방에 담을 수 있는 최대 가치의 보석을 담되 용량이 작은 가방부터 보석을 담는다.

가방의 순서를 신경쓰지 않고 보석을 담는다면 보석을 담지 못하는 경우가 생긴다.

 

풀이는 다음과 같다.

코드를 천천히 보면 이해가 될 것이다.

import sys, 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
temp = []

for bag in bags:
    while jewels and bag >= jewels[0][0]:
        heapq.heappush(temp, -jewels[0][1]) # max_heap
        heapq.heappop(jewels)

    if temp:
        ans += heapq.heappop(temp)
    elif not jewels:
        break

print(-ans)