1. 문제 설명

순회강연

2. 문제 분석

우선순위 큐를 통해 고비용 순서대로 강연을 뽑아, 가장 늦게 강연할 수 있는 날부터 카운트하면서 해당 날짜 별 얻을 수 있는 이득을 기록한다.

• 현 시점에서 힙에 존재하는 가장 이득이 큰 강연을 노트(nodes)에 기록한 이득과 비교하는 과정은 그리디와 유사하다는 느낌이 들었다.

3. 나의 풀이

import heapq
import sys

n = int(sys.stdin.readline().rstrip())
nodes = [0 for _ in range(10001)]
# 해당 날에 강연한 금액을 기록한다.
heap = []
for _ in range(n):
    p, d = map(int, sys.stdin.readline().rstrip().split())
    heapq.heappush(heap, [-1 * p, d])
    # 고비용 순서대로 기록

while heap:
    p, d = heapq.heappop(heap)
    p = -1 * p

    for idx in range(d, 0, -1):
        # d일 안에만 하면 되므로 가장 늦게 강연을 하는 기준
        if nodes[idx] < p:
            # 같은 날 다른 강연에서 받는 금액보다 크다면 바꾼다.
            nodes[idx] = p
            break

print(sum(nodes))