백준 #2109 순회강연

문제 설명

d일 안에 와서 강연을 해주면 p만큼의 강연료를 받는 여러개의 강의가 주어진다. d일동안 강연료를 최대로 받아야하는 문제

코드

import sys
input = sys.stdin.readline
from heapq import heappop, heappush


n = int(input())
hq = []
arr = []
for _ in range(n):
    p, d = map(int, input().split())
    arr.append((p, d))

arr.sort(key=lambda x:(x[1], -x[0]))

day = 0
for p, d in arr:
    if d > day:
        day = d

    if day == d:
        heappush(hq, p)
        while len(hq) > day:
            heappop(hq)

ans = 0
while hq:
    ans += heappop(hq)

print(ans)

풀이

d와 p를 받아와서 d를 기준으로 오름차순 정렬, 그리고 p를 기준으로 내림차순 정렬 후에 우선순위 큐를 이용해서 풀었다. 최초의 day를 0으로 설정 후에 받아온 d와 p를 가지고 만약 day가 현재 d를 따라가지 못한다면, 즉 d보다 작다면 day를 d로 설정해주었다. day와 d가 일치한다면 받아온 p를 넣어주고 day 길이 만큼의 강연료들만 남겨주었다. 마지막으로 하나씩 pop해주면서 더해주었다.

이게 얼마만의 포스팅이지…ㅜ