[백준] 1781 : 컵라면

JIN·2022년 1월 20일
0

우선순위 큐

컵라면

먼저 데드라인 순서대로 정렬을 하고 , 데드라인이 남은 과제면 일단 우선순위 큐에 넣었다.
이 때 우선순위 큐의 길이는 현재 몇일이 지났는지 알 수 있다.
그리고 데드라인 넘었지만 우선순위 큐에 0번째 요소가 현재 받을 수 있는 컵라면 개수 보다 작다면
우선순위 큐에 있는 가장 작은 값을 뺐을 때 데드라인이 하루 늘기 때문에 현재 컵라면 개수를 넣으면 된다
과제
이 문제랑 아예 똑같은 문제이다

import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
	dead, cup = map(int, input().split())
	lst.append((dead, cup))
lst.sort(key=lambda x:x[0])
answer = []
for i in range(len(lst)):
	if len(answer) < lst[i][0]:
		heapq.heappush(answer, lst[i][1])
	else:
		if answer[0] < lst[i][1]:
			heapq.heappop(answer)
			heapq.heappush(answer, lst[i][1])
print(sum(answer))
profile
배우고 적용하고 개선하기

0개의 댓글