[Algorithm] 백준 BOJ 13904 과제(python 파이썬)

BOJ 13904 과제

문제

웅찬이는 과제가 많다. 

하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다.

과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 

웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

시간 제한 : 1 초
메모리 제한 : 256 MB

입력

첫 줄에 정수 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

힌트

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

풀이

import sys

input = sys.stdin.readline
n = int(input().rstrip())
arr = []
res = [0 for _ in range(1000)]

for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])

arr.sort(reverse= True, key = lambda x : x[1])

for i in range(n):
    for j in range(arr[i][0]-1, -1, -1):
        if res[j] == 0:
            res[j] = arr[i][1]
            break

print(sum(res))