[BOJ 13904 🥇3] 과제 (Python)

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

13904번: 과제

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

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

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

출력

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

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

 

⭕ CODE

import heapq

n = int(input())

arr = []

for _ in range(n):
	# a : 마감일까지 남은 일수
    # b : 과제 점수
    a,b = map(int,input().split())
    arr.append([a,b])

# 마감일이 낮은거 부터 조사해야하므로 정렬
arr.sort()

result = []

for i in range(n):
	# 우선순위 큐에 arr[i][1] 즉 과제 점수를 넣어준다
    heapq.heappush(result,arr[i][1])
	# arr[i][0] : 마감일까지 남은 일수
    # 마감일까지 남은 일수가 result길이보다 짧다면
    # 마감일을 넘은거므로
    if arr[i][0] < len(result):
    	# 작은값부터 빼준다.
        heapq.heappop(result)
# 모든 과제 점수를 더해준다
print(sum(result))

✏️ Comment

https://jun-bae.tistory.com/44 와 동일한 문제

[BOJ 1781🥇2] 컵라면 (Python)