[Python/파이썬] 백준 1781번: 컵라면

문제

 

풀이

1. 데드라인을 기준으로 오름차순 정렬

문제 배열

데드라인	1	1	2	2	3	3	6
컵라면	7	6	4	5	1	2	1

 

2. 우선순위 큐에 첫 번째 문제를 넣는다.

우선순위 큐

날짜	1일	2일	3일	4일	5일
데드라인	1
컵라면	7

1일 차, 1문제

우선순위 큐에 문제를 삽입 = 해당 문제를 품

만약 우선순위 큐에 2개의 문제를 삽입했다면, 2일이 지난 셈이다. (한 문제당 하루가 걸리므로)

 

 

3. 우선순위 큐에 두 번째 문제를 삽입

우선순위 큐

날짜	1일	2일	3일	4일	5일
데드라인	1	1
컵라면	6	7

2일 차, 2문제

2일차일 때 데드라인이 1일까지인 문제는 풀 수 없다!

 

또한 동호는 마지막에 삽입된 데드라인보다 많은 문제를 풀 수 없다.

 

따라서 마지막에 삽입된 문제의 데드라인 < 현재 날짜인 경우

현재 날짜를 마지막에 삽입된 문제의 데드라인에 맞춰주면 된다.

즉, 컵라면이 가장 작은 문제를 풀지 않은 셈 치면 된다. (우선순위 큐 pop)

(문제는 우선순위 큐에 데드라인의 오름차 순으로 삽입되므로 우선순위 큐에는 항상 마지막에 삽입된 문제의 데드라인보다 작거나 같은 문제들만 존재한다. 따라서 한 문제 이상 풀지 않은 셈 칠 수 있다.)

 

우선순위 큐 (가장 작은 컵라면 pop)

날짜	1일	2일	3일	4일	5일
데드라인	1
컵라면	7

1일 차, 1문제

 

컵라면이 6인 문제를 풀지않은 셈 쳐서

현재 날짜를 2일 -> 1일로 맞춰준다.

 

위 과정을 반복하면 된다.

 

이해가 어렵다면

데드라인	1	2	3	3
문제	1	5	50	100

해당 데이터를 가지고 직접 해보길 바란다.

 

코드

import sys, heapq

input = sys.stdin.readline

n = int(input())

problems = [list(map(int, input().split())) for _ in range(n)]
problems.sort()
queue = []
for deadline, cupRamen in problems:
    heapq.heappush(queue, cupRamen)
    if deadline < len(queue):
        heapq.heappop(queue)

print(sum(queue))

 

마무리

너무 어렵다...