웹찢남

[백준 1202 보석 도둑 문제] PYTHON 본문

백준 Algorithm

[백준 1202 보석 도둑 문제] PYTHON

harry595 2021. 9. 9. 22:33

 

우선 보석 리스트와 가방 리스트를 받아 정렬한다.

그 후 힙을 사용하여 문제를 해결해야한다.

가방을 기준으로 for문을 돌리는데 이때 가방은 sort되어 무게가 작은 순으료 값이 나온다.

 

여기서 생각해야 할 점은 보석도 무게를 기준으로 sort 했기 때문에

보석을 heap에 넣어 놓고 다음 for 문 루프를 돌아도 heap에 있는 보석은 다음 가방 속에도 들어갈 수 있다.

 

그렇다면 heap에 보석을 넣을 때 maxheap으로 값을 넣고

for문이 돌때마다 가방에 들어갈 수 있는 보석을 업데이트 하며

heap 속에 들어있는 가장 가치있는 보석을 pop 하여 result에 값을 더하면

답이 나오게 된다.

 

처음에는 단순히 이중 포문으로 문제를 해결하려 했으나, 역시나 안된다. 

 

import sys
import heapq
input = sys.stdin.readline

Nlists = []
Klists = []
N, K = map(int, input().split())

for _ in range(N):
    a, b = map(int, input().split())
    Nlists.append([a, b])

for _ in range(K):
    c = int(input())
    Klists.append(c)

Nlists.sort()
Klists.sort()

result = 0
tmp = []
for Klist in Klists:
    while Nlists and Klist >= Nlists[0][0]:
        heapq.heappush(tmp, -Nlists[0][1])
        heapq.heappop(Nlists)
    if tmp:
        result += heapq.heappop(tmp)
    elif not Nlists:
        break
print(-result)
Comments