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

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

# 보석 도둑
import sys
import heapq
input = sys.stdin.readline

N, K = map(int, input().split())
gem = []
for _ in range(N):
    weight, cost = map(int, input().split())
    heapq.heappush(gem, (weight, cost))

bags = []
for _ in range(K):
    w = int(input())
    bags.append(w)
bags.sort()

result = 0
temp = []
for bag_weight in bags:
    while gem:
        if bag_weight >= gem[0][0]:
            weight, cost = heapq.heappop(gem)
            heapq.heappush(temp, -cost)
        else:
            break
    if temp:
        result -= heapq.heappop(temp)
print(result)

 

자료구조(힙)

1. 보석을 gem리스트에 최소힙으로 push (무게 기준)

2. bags 리스트에 가방의 한도무게를 append하고 오름차순 정렬

3. 가방 개수 만큼 반복

    - 가방 한도무게 >= gem리스트의 가장 작은 무게 이면 temp리스트에 최대힙으로 push

    - 해당 가방의 한도무게보다 작은 무게를 가진 보석들(temp리스트) 중에서 가치가 가장 큰값을 result에 더해줌

4. result출력

 

조금 꼬았는데 솔루션 찾기까지 오래걸렸다..