[python] 백준 1781 컵라면

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

1781번: 컵라면

 

문제 해결

• 데드라인을 생각하면서 컵라면 수가 큰 것을 스택 안에 넣는 문제
• 스택 안의 원소의 개수를 데드라인이라고 생각하면 된다.
• 그러면 스택 안에 원소를 데드라인이 빠른 것부터 처리를 하며 만약 컵라면은 많이가져갈 수 있는데 데드라인이 걸리면 그 전에 작은 컵라면수를 빼고 넣으면 된다.

CODE

import heapq
n = int(input())
table = []

for _ in range(n):
    d, c = map(int, input().split())
    table.append((d,c))
table.sort()

stack = []

for i in table:
    heapq.heappush(stack,i[1])
    if i[0] < len(stack):
        heapq.heappop(stack)
print(sum(stack))