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

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

1202번: 보석 도둑

import sys
import heapq
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())

jewelries = sorted([list(map(int, input().split())) for _ in range(N)])
bags = sorted([int(input()) for _ in range(K)])

# 메인 로직
valueSum = 0  # 출력값
availableJewelries = []  # bag 이하인 보석들을 저장
jewelryIndex = 0

for bag in bags:
    while jewelryIndex <= N-1:
        if jewelries[jewelryIndex][0] > bag:
            break

        heapq.heappush(availableJewelries, (-1)*jewelries[jewelryIndex][1])
        jewelryIndex += 1

    if availableJewelries:
        valueSum += (-1)*heapq.heappop(availableJewelries)

print(valueSum)

우선 보석과 가방을 모두 무게 순으로 정렬한다.

 

이후 가방들을 for문으로 돈다.

보석들을 탐색하면서, 해당 보석의 무게가 현재 가방의 수용 무게 이하이면 availableJewelries에 우선순위큐를 이용해 저장한다.

다음은 출력할 valueSum에 availableJewelries의 최대값을 넣어주면 된다.

여기서, availableJewelries이라는 존재가 가장 중요하다. bags에 대해 for문을 돌면서 jewelryIndex는 결국 0부터 N-1까지 증가하게 되는데, 보석들이 무게 순으로 정렬되어 있으며 availableJewelries에 훔치지 않은 보석은 남아있으므로, 이전에 고려했던 보석들은 무시해도 된다.