https://www.acmicpc.net/problem/2109
알고리즘 분류
- 그리디
- 우선순위큐
문제풀이
만약 3개 대학, (1,1), (10,2), (10,2)과 같은 경우 출력값은 무엇인가?
정답은 20이다.
리스트를 d값 기준으로 오름차순으로 정렬한다.
순간순간 최소값을 구해줄수있는 힙큐 모듈을 사용했다.
p값을 그때그때 우선순위큐에 넣어주는데 그 목록이 몇일안에 해야하는 마감일을 넘긴 경우 가장작은 값을 제거해준다.
소스코드
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))