문제

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

코드

import heapq

n=int(input())
lst=[]
for i in range(n):
  lst.append(list(map(int, input().split())))

lst.sort(key=lambda x: x[1])

p_list=[]
for i in lst:
  heapq.heappush(p_list, i[0])
  if (len(p_list)>i[1]):
    heapq.heappop(p_list)

print(sum(p_list))

• 그리디 + heap문제이다.

• 날짜 순으로 정렬 후에 마감일 내에 최대합의 값을 만들어내는 코드이다.

• 처음에는 날짜에 해당하는 날에만 수업을 할 수 있는 줄알고 코드를 짰지만, 문제를 잘읽어보니 d일 이내에 라는 말이 명시되어있었다.

• 그렇기에, (1,1),(20,2),(20,2) 이런식으로 오면 합은 21이 아닌 40이 되어야한다.

• 이를 위에 날짜순으로 정렬 후 기한이 넘은 경우에만 최소힙을 통해 가지고 있는 가장 작은 값을 빼내면된다.