2022.02.17 [백준] (python 파이썬) 보석 도둑

 

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

1202번: 보석 도둑

---

풀이

이 문제는 최대 힙과 최소 힙을 모두 사용했다.

우선 보석의 무게와 가격을 무게에 대한 최소힙으로 정렬, 가방이 담을 수 있는 무게는 리스트에 담아 오름차순 정렬해주었다. 그리고 for문으로 가방에 담을 수 있는 무게의 보석을 jewel_2힙에 -가격으로 저장했다. 이유는 최대 힙으로 만들어 넣을 수 있는 보석 중, 가장 비싼 보석을 뽑아내기 위해서이다. 

import heapq
import sys
 
input=sys.stdin.readline
 
n,k=map(int, input().split())
jewel=[]
bag=[]
#보석의 무게와 가격을 jewel힙에 추가
#이 때 무게해 대한 최소 힙
for _ in range(n):
    x,y=map(int,input().split())
    heapq.heappush(jewel,(x,y))
 
#배당에 담을 수 있는 무게를 bag리스트에 담고
#오름차순으로 정렬
for _ in range(k):
    x=int(input())
    bag.append(x)
bag.sort()
 
cost=0
#wight보다 작은 무게의 보석을 담을 힙
jewel_2=[]
 
for wight in bag:
    #jewel에 데이터가 있고 wight보다 보석의 무게가 작거나 같으면
    #jewel에서 꺼내고 jewel_2에 -가격 으로 저장(가격에 대한 최대 힙)
    while jewel and wight>=jewel[0][0]:
        heapq.heappush(jewel_2, -heapq.heappop(jewel)[1])
    #jewel_2에 보석이 들어있으면 그 중, 가장 비싼 보석을 꺼내줌.
    if jewel_2:
        cost-=heapq.heappop(jewel_2)
    #jewel_2가 비어있고, jewel또한 비어있으면 더 이상 가방에 넣을 보석이
    #없으므로 break
    elif not jewel:
        break
 
print(cost)