[백준] 1781번 컵라면

문제

입력

• 첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

• 첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

풀이

# [백준] 1781번 컵라면
import heapq
import sys

input = sys.stdin.readline

n = int(input())
# 정보를 담아놓을 리스트
array = []

for i in range(1,n+1):
    d,c = map(int,input().split())
    array.append((d,c))
array.sort()

q = []
for i in array:
    heapq.heappush(q,i[1])
    # 데드라인을 넘어선 문제는 빼낸다.
    if i[0] < len(q):
        heapq.heappop(q)
print(sum(q))

후기

처음에 문제를 풀 때는 어떤 알고리즘을 써야 해결할 수 있을까가 제일 고민이었는데, 이 알고리즘은 최소 힙 자료구조를 사용해야 풀 수 있는 문제였다. 항상 생각하지만 시간초과를 극복하는게 제일 어려운 거 같다. 아마 그 이유는 아직 시간 복잡도를 계산하는게 익숙하지 않아서 그런 거 같다. 추가로, 이 아이디어를 떠올리는게 참 어려웠다. 조금 더 연습해야지