[그리디/백준] 13904번 : 과제(다시)

-문제 : https://www.acmicpc.net/problem/13904

 

-정답 풀이 : 

 

모든 과제를 다 하지 않아도, 마감일 기준으로 점수가 최대인 과제들만 하면 된다. 

순차로 했을 때 어려운 문제는 거꾸로 진행하는 방법 잊지말자!!!!

 

ans 리스트의 인덱스는 마감일을 의미한다. ans[i]는 i일까지 할 수 있는 과제 중 가장 큰 점수이다.

예제에서 ans=[30,50,40,60,0,5]

점수가 최대인 것들을 기준으로 내림차순으로 정렬한 다음, 마감 전날에만 하면 마감일에 과제를 마칠 수 있으므로 work[i][0]-1부터 거꾸로 시작한다. 

n=int(input())
work=[]
ans=[0]*1000
for _ in range(n):
    work.append(list(map(int,input().split())))
    
work.sort(reverse = True, key = lambda x: x[1])    

for i in range(n):
    for j in range(work[i][0]-1,-1,-1):
        if ans[j]==0:
            ans[j]=work[i][1]
            break
print(sum(ans))