백준 1202 파이썬**

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

1202번: 보석 도둑

 

import heapq
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    jewels = []
    bags = []
    for _ in range(N):
        M, V = map(int, sys.stdin.readline().rstrip().split())
        heapq.heappush(jewels, (M, V))

    for _ in range(K):
        heapq.heappush(bags, int(sys.stdin.readline()))

    ans = 0
    capable = []
    for _ in range(K):
        bag = heapq.heappop(bags)
        while jewels and bag >= jewels[0][0]:
            weight, value = heapq.heappop(jewels)
            heapq.heappush(capable, -value)
        if capable:
            ans -= heapq.heappop(capable)
        elif not jewels:
            break

    print(ans)

 

이 문제는 우선순위 큐를 이용하면 풀 수 있는 문제다.

문제를 풀 수 있는 핵심 아이디어를 생각하기까지 많이 고민해야하는 문제이다.

 

1. 보석을 무게를 기준으로 우선순위큐에 담는다.

 

2. 가방을 우선순위큐에 담는다.

 

3. 가방의 갯수만큼 순회하면서 가방을 pop 한다

 

4. pop한 가방의 용량에 담을 수 있는 무게의 보석 전체를 우선순위 큐에 최대힙으로 저장한다. 

(최대힙으로 저장하기 위해 음수로 담는다)

 

5. 현재 가방에 담을 수 있는 보석 중 첫번째를 꺼내 결과에서 뺀다.

- 결과에 더하지않고 빼주는 이유는 최대힙으로 하기위해 보석의 가치를 음수로 저장했기 때문에 빼줘야 양수가 되기 때문이다.

- 보석 중 첫번째를 꺼내는 이유는 최대힙으로 저장했기 때문에 현재 가방이 담을 수 있는 최대 가치의 보석이 보장되기 때문이다.

 

6. 남은 보석이 없다면 루프를 종료한다.