[백준]1781 컵라면 #그리디#힙

1. 풀이

모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다.

이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다.

 

2. 소스코드

from collections import deque
import heapq

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

# t시간까지 해야되는거 pq에추가
def addPQ(t):
    while(L):
        dead,cup=L.pop()
        if dead==t:
            heapq.heappush(cupPQ,-1*cup)
        else:
            L.append([dead,cup])
            return

L.sort()
L=deque(L)
cupPQ=[]
ans=0
for i in range(N,-1,-1):
    # 현재 해야되는거(컵라면가장많은거) 하기
    if cupPQ:
        ans+=-1*heapq.heappop(cupPQ)
    # 후보 추가
    addPQ(i)


print(ans)