2109. 순회강연 (Python)

 

2109번: 순회강연

 

풀이

 뒤에 날짜부터 앞으로 이동해가며 현재 날짜에 강연할 수 있는 강연 리스트 중 가장 높은 강연료를 받을 수 있는 강연을 선택하도록 구현하면 된다. 이를 위해 두 개의 최소힙을 사용하여 하나의 힙에는 모든 강연을 담아두고 뒤에 날짜에 있는 강연들을 하나씩 꺼내가며 현재 날짜에 강연이 가능한 강연들의 강연료에 대하여 또 다른 최소힙에 담아주고 날짜가 바뀔 때마다 해당 최소힙에서 가장 높은 강연료를 꺼내어 더해나간다.

 

코드

import sys
import heapq
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())

    maxDay = 0 # 강연 중 가장 기한이 긴 날짜
    q = [] # 강연들을 담아두는 힙 -> (-날짜, 가격)
    priceQ = [] # 현재 강연이 가능한 강연들의 가격을 담아두는 힙 -> (-가격)

    for _ in range(N):
        p, d = map(int, input().split())
        maxDay = max(maxDay, d)
        heapq.heappush(q, (-d, p))

    res = 0

    # maxDay부터 1일까지 거꾸로 진행 
    for day in range(maxDay, 0, -1):
        while q: # q에서 강연 정보를 하나씩 꺼내어 현재 날짜에 강연이 가능한 강연인지 체크한다.
            d, p = heapq.heappop(q)
            d *= -1

            if day > d: # 불가능한 강연이라면 다시 q에 집어넣고 종료한다.
                heapq.heappush(q, (-d, p))
                break

            heapq.heappush(priceQ, -p)

        if priceQ: # 현재 날짜에 강연 가능한 강연들이 있다면 제일 높은 가격을 가진 강연을 강연한다.
            res += -heapq.heappop(priceQ)

    print(res)