[백준] 13904번 - 과제 (파이썬)

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

 

# 과제
import heapq
from collections import defaultdict
N = int(input())

arr = defaultdict(list)
for _ in range(N):
    dday, score = map(int, input().split())
    arr[dday].append(score)

q = []
answer = 0
now = max(arr.keys())
while 0 <= now:
    if q:
        score = heapq.heappop(q)
        score = -score
        answer += score
    for x in arr[now]:
        heapq.heappush(q, -x)
    now -= 1

print(answer)

 

자료구조, heapq
1. 각 남은 일수의 점수 리스트를 딕셔너리로 만든다.
2. 각 날짜별로 최대 점수 하나씩 포함 (역순으로)
    - q가 있다면 가장 큰 score를 포함
    - 최대 dday부터 1씩 빼가면서 우선순위 큐에 포함
3. answer 출력

 

뒤에서부터 해당 dday를 q에 넣으면서 가장 큰 점수를 하나씩 포함해나가면 된다.

ex) 마감기간이 최대 6일일 경우
1일 차 : 1~6일 차에서 가장 큰 점수
2일 차 : 2~6일 차에서 가장 큰 점수
...
6일 차 : 6일 차에서 가장 큰 점수