백준 13904번: 과제 (파이썬)

https://www.acmicpc.net/problem/13904

13904번: 과제

 

문제

 

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

 

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력

 

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

 

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

출력

 

얻을 수 있는 점수의 최댓값을 출력한다.

 

풀이

 

얻을 수 있는 점수를 최대로 만들기 위해서는 점수가 높은 과제를 최대한 많이 해야 한다는 것은 당연하다. 그렇다면 그 과제를 언제 하는 것이 맞을까?

이전의 다양한 그리디 문제 풀이 경험에서, 이런 경우 보통 due date에 가깝게 과제를 하는 것이 최적의 방법임을 떠올렸고, 해당 방법대로 코드를 구현했다.

 

소스 코드

 

n = int(input())

hw = []
for i in range(n):
    d, w = input().split()
    d, w = int(d), int(w)
    hw.append((d, w))
hw.sort(reverse = True, key = lambda x : x[1])

sum = 0
valid = [False] + [True for i in range(1000)]
for i in range(n):
    date = hw[i][0]
    while not valid[date] and date != 0:
        date -= 1
    if valid[date]:
        valid[date] = False
        sum += hw[i][1]
print(sum)