[BOJ] 백준 1781번: 컵라면

1일 1PS 20일차!

📚 문제

---

골드 2

• 입력받는 줄의 수가 많기 때문에 sys 를 사용해 입력 받는 것을 추천한다.
• 특정 상황에 대해서 가장 높은 컵라면 문제부터 풀어야하므로 MaxHeap 을 사용한다.
• 순서대로 보자면 데드라인이 높은 것도 낮은 시간에 풀 수 있기 때문에 처음에는 모든 문제를 풀 수 있고 시간이 지나갈 수록 데드라인이 지난 문제를 못풀기에 MaxHeap 에서 제거해야한다. 또한 데드라인에 가까울 수록 우선순위를 가져야한다.
• 반대로 시간을 끝에서부터 거꾸로 바라보자.
  • 시간이 줄어듦에 따라 데드라인이 충족되는 문제들을 push 한다.
  • 각 시간마다 컵라면 수가 가장 큰 문제를 pop 한다.
• 파이썬에서는 MinHeap 뿐이므로 -1 을 곱해 MaxHeap 처럼 사용한다.

💡 포인트

---

1. MaxHeap 을 생성한다.
2. 데드라인에 따라 MaxHeap 에 추가하기 위해서 deadlines[][] 를 생성한다. deadline 이 i 인 문제들이 deadlines[i] 에 저장된다.
3. 시간을 N 부터 1까지 거슬러가면서 i 시간에 MaxHeap 에 deadlines[i] 에 있는 문제들의 컵라면 수를 추가한다.
4. 시간이 지날때마다 MaxHeap 에 요소가 존재하면, pop 을 통해 가장 큰 컵라면 수를 cnt 에 추가한다.

💻 코드

---

import sys
import heapq

n = int(sys.stdin.readline())
deadlines = [[] for _ in range(n + 1)]
cups = [0 for _ in range(n)]
maxHeap = []
cnt = 0

for i in range(n):
    deadline, cup = map(int, sys.stdin.readline().split())
    deadlines[deadline].append(i)
    cups[i] = cup


for i in range(n, 0, -1):
    for deadline in deadlines[i]:
        heapq.heappush(maxHeap, (-1) * cups[deadline])
    if maxHeap:
        cnt += heapq.heappop(maxHeap)

print( cnt * (-1))