[BAEKJOON] #1202) 보석 도둑 (그리디, 최소힙)

백준 1202 보석 도둑 파이썬 문제 풀이입니다.

1202번: 보석 도둑

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1202 보석 도둑

import sys
import heapq

input = sys.stdin.readline

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

jewelries = [tuple(map(int, input().split())) for _ in range(n)]
bags = [int(input()) for _ in range(k)]

jewelries.sort()
bags.sort()

tmp = []
result = 0

for bag in bags:
    while jewelries and jewelries[0][0] <= bag:
        heapq.heappush(tmp, -jewelries[0][-1])
        heapq.heappop(jewelries)

    if tmp:
        result -= heapq.heappop(tmp)

print(result)

• 아이디어는 용량이 작은 가방부터 담는 것입니다. 그리고 가방에 담을 수 있는 보석 중 가격이 가장 높은 보석을 담습니다.
• 우선, 보석과 가방 리스트 모두 정렬이 되어 있어야합니다. 용량이 작은 가방부터 담아야하고, 가방에 넣을 수 있는지 가장 작은 것부터 차례대로 확인해야하기 때문입니다.
• 그리고 나서, 정렬된 보석 리스트에서 0번 인덱스를 확인하여 가방에 넣을 수 있는지 확인합니다. 가방의 용량보다 작은 보석들을 tmp 리스트에 넣습니다. 이때 중요한 것은 heapq 모듈을 사용해서 가격이 가장 비싼 보석이 맨 앞에 오도록 넣는 것입니다! (파이썬 내장 모듈인 heapq는 최소 힙만 지원하므로 가격을 음수로 만들어서 최소 힙에 넣습니다.)
• tmp에 넣은 보석은 jewelries 리스트에서는 pop해줍니다.
• 가방에 넣을 수 있는 보석을 모두 tmp에 넣었으면 최종적으로 넣을 보석을 선택합니다. 가장 비싼 보석이 음수를 달고 tmp 리스트의 맨 앞에 있을 것이므로 result에는 tmp에서 pop한 값을 빼줍니다.(현재 가격이 음수이므로)