[백준/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

N = int(input())
N_list = []
ans_list = []
cnt = 0

for i in range(N) :
    d, w = map(int, input().split())
    N_list.append([d,w])
N_list.sort()
deadline = N_list[-1][0]

for i in N_list :
    if not (ans_list) :
        heappush(ans_list, i[1])
        cnt += 1
        continue

    if cnt >= deadline or i[0] <= cnt :
        heappush(ans_list, i[1])
        heappop(ans_list)
    else :
        heappush(ans_list, i[1])
        cnt += 1

print(sum(ans_list))

 

풀이

과제 목록을 입력받은 후 정렬한다. 이 후, 우선 순위 큐인 리스트에 과제를 하나씩 삽입한다. 이 때, 삽입한 과제 개수를 카운트하면서 가장 마지막날에 수행하는 과제의 수행일보다 크거나, 이미 수행하기로 한 과제의 개수보다 삽입하려하는 과제의 수행일이 크다면 우선 순위 큐에서 삽입한 후, 하나를 삭제한다.