[파이썬] [그리디] 백준 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

 

코드

N=int(input())
array=[list(map(int,input().split())) for _ in range(N)]

array.sort()
result=[0]*1000

for d,w in array:
    if result[d-1]==0:
        result[d-1]=w
    else:
        max=100
        for i in range(d):
            if max>=result[i]:
                max=result[i]
                index=i
        result[index]=w
        
print(sum(result))

생각 정리

값이 없는 새로운 배열을 만들어 최소값이랑 swap하도록 구현하였다.