[백준] 1781번: 컵라면

문제

백준 - 1781번: 컵라면

분석

n개의 문제에 대한 데드라인과 얻을 수 있는 컵라면 수가 주어질 때,
받을 수 있는 최대 컵라면 수를 구하는 문제이다.

처음에 문제를 푸는데 1시간이 걸린다고 해서, 동일한 데드라인이면 그 중 하나만 풀 수 있다고 생각해서 풀었다가 틀렸다.

동일한 데드라인이어도 남은 시간이 있다면 여러개도 끝낼 수 있다. 또한, 데드라인이 빠른 것을 먼저 해치우는 경우보다 당장 데드라인인 것을 해치우지 않고 뒤에 것을 푸는 경우에 컵라면을 더 많이 얻을 수 있는 경우도 존재한다.

먼저 데드라인과 얻을 수 있는 컵라면을 튜플로 받아 리스트에 추가한 후, 정렬한다.
이렇게 하면 데드라인이 작은 것이 가장 우선순위고, 그 다음 컵라면이 작은 것이 우선으로 정렬된다.

그리고 리스트를 차례로 순회한다. 일단 우선순위 큐에 현재 참조하는 컵라면 수를 넣는다.
큐의 길이는 문제 푸느라 지난 시간을 의미한다고 할 수 있다. 이것이 데드라인 보다 크다면 큐에서 pop을 하여 가장 컵라면 수가 작은 값을 뺀다. 모든 순회를 마치고 우선순위 큐에 남은 값들을 sum하면 최대 컵라면 수를 구할 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from heapq import heappush, heappop
n = int(input())
lst = []
pq = []
for _ in range(n):
    deadline, cup = map(int, input().split())
    lst.append((deadline, cup))
lst.sort()

for d, c in lst:
    heappush(pq, c)
    if len(pq) > d:
        heappop(pq)
print(sum(pq))

끝으로..

예외 케이스를 충분히 고려하지 않고 풀었다가 처음에 틀렸는데,
앞으로 더 신중하게 케이스를 고민해 봐야겠다.