백준(1202) - 보석 도둑 Python

백준(1202) - 보석 도둑

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

오름차순 정렬된 가방무게 순서대로 담을 수 있는 무게중 가장 큰 보석을 담아가면서 결과를 출력해야하는데 쉽지 않았던 문제였다.

우선순위 큐를 사용해야 풀리는 문제지만 생각해내지 못하고 구글링을 하고 난 뒤에 해결방법을 보고 푼 문제이다.

가방과 보석을 오름차순으로 정렬시킨다면,

보석을 비교할때 이전 가방에 담을 수 있는 보석은 현재 가방에서도 담을 수 있기 때문에 담을 수 있는 무게의 보석들은 모두 heappush() 해주면 된다, 그리고 담겨 있는 가방에서 가장 무거운 보석만 heappop() 해줘서 결과값에 더해주면 된다.

1. 가방과 보석을 오름차순으로 정렬한다.
2. 가방을 순차적으로 비교한다.
   1. 보석도 무게가 적은 것부터 하나씩 확인하면서 담을 수 있는 무게면 그 보석의 cost를 우선순위 큐에 담는다.(우선순위 큐의 기본은 최소 힙이므로 -를 앞에 붙여서 담아야 최대 힙이 된다.)
   2. 담겨진 보석들 중 가장 무거운 보석을 꺼낸다(-값을 넣었으므로 절대값 abs()를 붙여준다.)
   3. 확인했던 보석은 다시 확인할 필요없으므로 check로 인덱스를 관리하면서 보석을 순차적으로 비교해준다.

import heapq
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
bosucks = []
for _ in range(n):
    weight, cost = map(int, input().split())
    bosucks.append((weight, cost))

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

result = 0
check = 0
q = []
for bag in bags:
    while check < n and bag >= bosucks[check][0]:
        heapq.heappush(q, -bosucks[check][1])
        check += 1
    if len(q) > 0:
        result += abs(heapq.heappop(q))

print(result)

# 이전의 가방보다 현재의 가방이 더 크기 때문에 이전 가방에 들어갈 수 있는 보석은
# 무조건 현재 가방에서도 가능하다. 따라서 우선순위 큐의 heapq를 사용하면 된다.