제로베이스 20220321

1. 컵라면

• 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다.
• 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호 1 2 3 4 5 6 7 데드라인 1 1 3 3 2 2 6 컵라면 수 6 7 2 1 4 5 1

• 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

• 문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

• 문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다.
• 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 2³¹보다 작거나 같은 자연수이다.

입력

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

출력

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

풀이

import sys
import heapq
from collections import deque

N = int(sys.stdin.readline())
 
heap = []

for i in range(0,N):
	deadline, noodle = list(map(int,sys.stdin.readline().split()))	
	heapq.heappush(heap,(deadline,-noodle))
 
selected = []
cnt = 0
while(len(heap) > 0):
	problem = heapq.heappop(heap)
	if problem[0] > cnt:
		heapq.heappush(selected,(-problem[1],problem[0]))
		cnt += 1
	elif -problem[1] > selected[0][0]:
		heapq.heappop(selected)
		heapq.heappush(selected,(-problem[1],problem[0]))
 
print(sum([x for x,y in selected]))

채점 결과

• 정답

리뷰

• 데드라인 내에 컵라면을 최대한 많이 확보해야 하므로 다음 조건을 얻을수 있다.
  1. 데드라인 순 정렬
  2. 데드라인이 같다면, 컵라면을 많이 확보할수 있는 순으로 정렬
• 위에서 정렬한 순서대로 넣으며 시간을 증가시키는데, 데드라인이 후순위에 있지만 컵라면이 많이 걸린 문제가 있을 경우, 컵라면을 가장 적게 주는 문제를 제거한다(pop)