[백준][Python]2109번(순회강연)

백준 2109번

✔️ 문제 풀이

◾ heapq 활용

• 1일차에는 1개의 강연이 가능, 2일차에는 2개의 강연이 가능
  (두번째 입력값은 2일차에 해야한다가 아니라 2일차까지 해야한다이기 때문에 이 값이 3이어도 1일차에 강연할 수 있다)
• 중요한건 현재 며칠이 지났는지와 강연의 개수
• 먼저 강연의 값과 기한을 lists에 입력받고, 이를 기한을 기준으로 오름차순 정렬한다.
• 강연할 리스트를 담을 array를 만들고, lists를 돌아가며 lists[i][1]의 값(강연 기한)이 array의 길이(현재 강연한 개수)보다 크면 무조건 array에 넣는다
• 같다면 array에 현재 탐색 중인 강연의 값을 담고, 담긴 강연 중 가장 값이 싼 강연을 pop한다.
• 각각의 강연을 며칠에 할 것인지는 중요하지 않고, 기한 내에 가능한 강연을 담았다는 것만 확인하면 된다.

최종 제출 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input().rstrip())
lists = []
for i in range(n):
  lists.append(list(map(int,input().split())))
  # heapq.heappush(lists, list(map(int,input().split())))
  
lists.sort(key=lambda x: x[1])

array = []

for i in range(n):
  if len(array) < lists[i][1]:
    heapq.heappush(array, lists[i][0])
  else:
    heapq.heappush(array, lists[i][0])
    heapq.heappop(array)

print(sum(array))