[백준] 2109 파이썬(python) : 순회강연 -(추가예시)

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

2109번: 순회강연

 

 

import sys, heapq
n = int(sys.stdin.readline())
lecture = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
lecture.sort(key=lambda x : x[1]) #1
heap = []
for i in lecture: #2
    heapq.heappush(heap, i[0]) #3
    if len(heap) > i[1]: #4
        heapq.heappop(heap)
print(sum(heap)) #5

 

#1 : 가장 많이 돈을 벌어야 하므로 강연료 기준으로 정렬

#2 : 들어온 강의 수 만큼 반복

#3 : 강연료를 heap에 삽입

#4 : len(heap)은 지금까지 강의하면서 쌓여온 강의료의 개수니까 지나온 날을 의미하므로 len(heap)이 현재 반복하는 강연의 마감일보다 크다면 강연을 하지 못하게 된다. 그래서 heap자료구조에서 가장 작은 값을 뺀다.

마감일은 그 전날까지만 일을 수행하면 된다. 마감일날 해야하는것이 아니기 때문에 마감일이 4인 강연을 3일차에 해도 된다. 

#5 : heap리스트의 값을 모두 더하면 가장 큰 강연료를 구할 수 있다.

 

추가 예시)

8
2 1
5 1
10 2
20 2
10 4
20 4
30 4
10 6

 

계속 쌓이다가 (30, 4)일때 마감일이 4일인 강연이 5일차에 수행되야 하기 때문에 앞에서 가장 작은값인 (5, 1)이 최소값이어서 삭제된다. 그리고 (10, 6)은 5일차에 강연한다.

 

최소값을 내보내서 최대값들만 남기게 만드는 방법을 사용하는데 처음엔 최대 힙 사용해야 하는 줄 알고 고민하다 안되서 블로그를 찾아봤다. 나는 왜 이런 생각을 할 수 없는지 우울하고 골드는 난이도가 높다고 느낀다.