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

힌트

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

 

N = int(input())
home_works =[]
ans=0
days =0

for index in range(N):
    work  = list(map(int, input().split(" ")))
    if work[0]> days:
        days = work[0]
    work.append(index)
    home_works.append(work)
home_works=sorted(home_works, key = lambda i:( -i[1],i[0]))

planner =[]
for _ in range(days+1):
    planner.append(-1)
for work in home_works:
    for i in range(work[0],0, -1):
        #print(i)
        if planner[i] ==-1:
            planner[i] = work[2]
            ans+=work[1]
            break
        
print(ans)