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

 

 

문제 링크

 

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

1202번: 보석 도둑

 

 

문제 풀이

 

전체 예제 테케에서는 무게가 무거운 보석이 더 비싼 가격이지만,

무게가 가벼운 보석이 더 비쌀 수도 있습니다.

간단한 예를 들어,

가방의 수용 무게 : 10 20

보석의 무게/가격 : 10/40 20/30

단순하게 넣을 수 있는 보석 중 최대 가격을 가지는 보석부터 순차적으로 넣는다고 해봅시다.

이 경우에 어떤 가방에 먼저 보석을 넣을 지에 따라 최대 결괏값이 달라지게 됩니다.

두 번째 가방부터 넣는다면 결괏값으로 40을 얻게 됩니다.

첫 번째 가방부터 넣는다면 결괏값으로 70을 얻게 됩니다.

 

결국, 수용 무게가 적은 가방부터 보석을 넣어야 하며

해당 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 넣는 것이 이 문제의 핵심입니다.

 

주어진 입력 범위가 매우 크며, 정렬된 상태를 항상 유지하며 최솟값을 가져와야하므로

heapq를 사용했습니다.

heapq는 기본적으로 heappop을 할 때 최솟값을 반환하므로,

최대힙을 만들기 위해서는 -를 붙여 push하면 됩니다.

 

temp = []   # 가방에 넣을 수 있는 보석의 가격 (= 가방의 무게보다 무게가 적은 보석의 가격)
for b in bag:
    while jewel and b >= jewel[0][0]:
        # 최대힙 생성
        heapq.heappush(temp, -heapq.heappop(jewel)[1])
    if temp:
        result -= heapq.heappop(temp)
    elif not jewel:
        break

 

jewel은 모든 보석의 무게, 값을 입력받은 최소힙입니다.

jewel에 원소가 존재하며 가장 앞 원소의 무게가 가방의 무게보다 작을 경우

temp라는 최대힙에 -를 붙인 가격을 넣어줍니다.

현재 가방보다 무게가 작거나 같은 보석을 모두 temp에 넣었을 경우

temp에서 최솟값을 꺼내주고 다시 -를 붙여주면 결국 최대 가격을 도출할 수 있습니다.

result += -heapq.heappop(temp)

temp에 가격은 다음 가방에 대한 보석을 확인할 때에도 남아있으므로,

가방에 넣은 보석을 제외한 모든 보석 중 최대 가격을 도출할 수 있습니다.

 

 

 

전체 코드

import heapq

n, k = map(int, input().split())
jewel = []
bag = []
for _ in range(n):
    heapq.heappush(jewel, list(map(int, input().split())))
for _ in range(k):
    bag.append(int(input()))
bag.sort()
result = 0
temp = []   # 가방에 넣을 수 있는 보석의 가격 (= 가방의 무게보다 무게가 적은 보석의 가격)
for b in bag:
    while jewel and b >= jewel[0][0]:
        # 최대힙 생성
        heapq.heappush(temp, -heapq.heappop(jewel)[1])
    if temp:
        result -= heapq.heappop(temp)
    elif not jewel:
        break
print(result)