백준 1781 컵라면

문제

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

풀이

n이 최대 20만이기 때문에 O(n^2)으로는 시간초과가 날 것이라 생각했다.
뭔가 선형적으로 탐색하며 넣고 빼고를 어떻게 잘 할 수 있을까 고민했다.

데드라인 기준으로 정렬 후, 물품을 하나씩 담는데,
현재 담은 물품의 개수보다 데드라인이 작아서 해당 물건을 넣지 못한다면,
제일 컵라면 수가 작은 물품을 빼고 큰 물품을 집어넣으면 된다.

import heapq
n = int(input())
arr = []
for i in range(n):
  a,b = list(map(int,input().split()))
  arr.append((a,b))
arr.sort()
q = []
for a,b in arr:
  heapq.heappush(q,b)
  if a < len(q):
    heapq.heappop(q)
print(sum(q))

맨 위로 이동하기

boj 카테고리 내 다른 글 보러가기