[백준/Python] 13904번: 과제

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

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

문제 코드

from heapq import heappush, heappop

hq = []

n = int(input())
point = 0
maxDay = 0


for _ in range(n):
    d, p = map(int, input().split())
    home = [-p, d]
    maxDay = max(maxDay, d)
    heappush(hq, home)
    
homework = [False] * (maxDay + 1)

while hq:
    p, d = heappop(hq)

    for i in range(d, 0, -1):
        if homework[i] == False:
            homework[i] = True
            point += -p
            break

print(point)

문제 풀이

1. 점수를 기준으로 우선순위 큐에 추가 (최대힙을 이용, 입력 점수을 음수로 변환)

2. homework 리스트를 통해 제일 높은 점수 순서대로 heappop 해주기

2-1. 해당 과제를 제일 마지노선에 수행하도록 배정

2-2. 배정과 동시에 총 점수에 추가