백준 1781 - 컵라면 (Python)

https://acmicpc.net/problem/1781 

1781번: 컵라면

알고리즘 수업 시간에 배웠던 잘 알려진 그리디 문제. 그때는 unit task scheduling problem이라고 배웠던 것 같다.
그리디 알고리즘임을 알기만 한다면 문제 풀이는 크게 어렵지 않다.

from heapq import heappop,heappush
import sys
input=sys.stdin.readline
INF=sys.maxsize
N=int(input())
noodles=[]

for _ in range(N):
    a,b=map(int,input().split())
    heappush(noodles, (a,-b))

visited=[]

while noodles:
    d,v=heappop(noodles)
    if not visited:
        visited.append(-v)
        min_val=-v
        min_idx=0
        continue
    if len(visited)<d:
        visited.append(-v)
        if -v<min_val:
            min_val=-v
            min_idx=len(visited)-1
    else:
        if -v<=min_val:
            continue
        else:
            visited[min_idx]=-v
            min_val=min(visited)
            min_idx=visited.index(min_val)

print(sum(visited))