[BOJ] 백준 1202번: 보석 도둑

1일 1PS 7일차!

문제

---

골드 2

• 골드 2 치고는 쉬운 문제같다.
• 최대, 최소값을 사용해야하기에 heap 을 사용한다.
  • 파이썬에서는 minHeap 만 존재하기에 -1 을 곱해서 maxHeap 처럼 사용한다.
• input 양이 많아서 import sys 를 하지 않으면 시간 초과가 발생한다!

포인트

---

1. 가방과 보석을 모두 가벼운 순서대로 정렬한다.
2. 가장 가벼운 가방에 들어갈 수 있는 보석들의 가치를 MaxHeap 으로 저장한다.
3. 매번 가방에 들어갈 수 있는 보석 중 가장 높은 가치의 보석을 가져온다.

코드

---

import sys
import heapq

input = sys.stdin.readline

n, k = map(int, input().split())

jews = []
bags = []

for _ in range(n):
    heapq.heappush(jews, list(map(int, input().split())))

for _ in range(k):
    heapq.heappush(bags, int(input()))

values = []
value = 0

while bags:
    bag = heapq.heappop(bags)
    while jews and jews[0][0] <= bag:
        heapq.heappush(values, -jews[0][1])
        heapq.heappop(jews)
    if values:
        value -= heapq.heappop(values)

print(value)