[BOJ 1202, Python 3] 보석 도둑

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

1202번: 보석 도둑

 

 

풀이

가방은 용량을 기준으로 내림차순으로 정렬하고, 보석은 무게 순으로 내림차순 정렬을 합니다.

그리고 (보석의 무게) <= (다음 가방의 무게)를 비교해보고 사용할 수 있는 가방에 해당 가방을 추가해주면 됩니다.

그래서 보석의 가치를 최소힙/우선순위큐에 저장하다가 가져가는 보석의 수가 (이용할 수 있는 가방의 길이)보다 커지면 제일 가치가 없는 보석을 버려주면 됩니다.

 

이게 왜 가능하냐면 보석과 가방 용량을 내림차순으로 확인하니 이용할 수 있는 가방의 용량들은 전부 현재 인덱스의 보석의 무게보다 크거나 같기 때문입니다. 따라서 아무 가방에나 넣어도 상관이 없습니다.

 

 

코드

from heapq import *
input = __import__('sys').stdin.readline
n, k = map(int, input().split())
arr = sorted([[*map(int, input().split())] for _ in range(n)], reverse=True)
bag = sorted([int(input()) for _ in range(k)], reverse=True)
use_bag = 0
idx = 0
ans = []
for i in range(n):
    while idx < k and bag[idx] >= arr[i][0]:
        use_bag += 1
        idx += 1
    heappush(ans, arr[i][1])
    if len(ans) > use_bag:
        heappop(ans)
print(sum(ans))