백준 온라인 저지, 그리디 / 13904번: 과제 (파이썬 / 백준 골드문제)

문제

https://www.acmicpc.net/problem/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

접근 방법

코드

# https://www.acmicpc.net/problem/13904
n = int(input())
work = [list(map(int, input().split())) for _ in range(n)]
work.sort()
dp = [0] * 1000
for d, w in work:
    if dp[d-1] == 0:
        dp[d-1] = w
    else:
        min_value = 100
        for i in range(d):
            if min_value > dp[i]:
                min_value = dp[i]
                index = i
        dp[index] = w
print(sum(dp))