2/4 Coding Test

✅ Coding Test

🎈 2109 순회강연

N개 대학에 순회 강연을 다니는데 각 대학에서 d일 안에 강연을 하면 p만큼의 강연료를 지불한다고 한다. 예시로 4개의 대학에서 각각 p, d로 50, 10, 20, 30 // 2, 1, 2, 1을 제시했을 때 첫 날 30, 둘째 날 50을 벌 수 있다.

입력값으로 첫 줄에 정수 N이 주이지고 다음 n줄 만큼 p,d가 주어질 때 최대로 벌 수 있는 돈을 구하기.

import sys, heapq
input = sys.stdin.readline

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

heap = []
for i in day:
    heapq.heappush(heap, i[0])
    if len(heap) > i[1]:
        heapq.heappop(heap)
print(sum(heap))

< 해설 >
강연 비용, 강연 날짜를 각자 리스트로 나누어서 처리할 수도 있지만, heap을 이용해 day를 오름차순으로 정렬하고 비용을 더하고 길이보다 길면 pop하는 방식으로 처리하면 보다 쉽게 최대로 벌 수 있는 돈을 처리할 수 있다.