[Python/파이썬] - 백준(BOJ) 13904번 : 과제

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

13904번: 과제

 

맥스 힙을 이용한 그리디 문제이다.

arr 배열을 1001개 만들어서 arr[마감기한].append(점수)를 해준다

이후 가장 긴 마감기한부터 짧은 마감기한까지 역순으로 for문을 돌려서 점수를 맥스 힙에 추가시켜준다

역순으로 돌리는 이유는 마감기한이 길면 마감기한이 짧은 것 처리 후에 해도 되기 때문이다.

이후 마감기한을 1씩 감소될때마다 heappop을 해서 answer를 증가시킨다. 

 

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
n = int(input())
heap = []
arr = [[] for _ in range(1001)]
m = 0
for _ in range(n):
    a, b = map(int,input().split())
    arr[a].append(b)
    if m < a:
        m = a

answer = 0
for i in range(m, 0, -1):
    for x in arr[i]:
        heappush(heap, -x)
    if heap:
        answer -= heappop(heap)
print(answer)