2109순회강연

https://www.acmicpc.net/problem/2109

2109번: 순회강연한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다.www.acmicpc.net

이전 ‘보석도둑’ 문제를 참고해서 풀었다.

먼저 날짜가 높은 순서대로 정렬하고,

강의를 마지막 날짜부터 1씩 감소시키면서,

현 날짜와 똑같은 날짜의 강의를 힙에 넣는다.

그후, 날짜가 하나씩 감소할 때마다, 힙에 남아있는 가장 큰 값을 넣는다.

import sysimport heapqinput = sys.stdin.readlinelect = []n = int(input())
if n==0:     print(n)    exit()for _ in range(n):
    p, d = map(int, input().split())    heapq.heappush(lect, (-d, p))  # 날짜, 강연료
lect.sort()  # 높은 날짜순서로 정렬h = []  # 최대힙answer = 0day = -lect[0][0]  # 마지막 나ㅣㄹ짜
while day > 0:  # 강의가 존재할 때까지
    while lect and -lect[0][0] == day:  # 강의가 존재하고, 강의의 제한시간과 같을 때
        heapq.heappush(h, -heapq.heappop(lect)[1])    if h:
        answer -= heapq.heappop(h)    day -= 1print(answer)

그런데 다 풀고 나서 다른풀이를 보니 더 간단한 방법이 존재했다.

강의를 날짜기 낮은 순으로 정렬하고,

반복을 돌면서, 무조건 heap에 pay를 넣는다. (여기서의 힙은 최소힙이다)

그 후, 만일 현재 날짜가 heap의 길이보다 크다면 (즉 비어있는 스케줄이 없다면)

heap의 가장 작은 날짜를 pop해줘서 날짜를 맞춰준다.

import sysfrom heapq import *input =sys.stdin.readlinen=int(input())
lect=sorted([[* map(int,input().split())]for _ in range(n)], key=lambda x: x[1]) #날짜기준으로 정렬
h=[] #최소힙for p,d in lect:    heappush(h,p) # 일단 무조건 힙에 pay를 넣는다.
    if len(h)>d: #만약, 강의가 모두 잡혀있는 상태라면        heappop(h) # 가장 pay가 적은 강의를 뺀다
print(sum(h))