[백준] 13904번 과제 (python)

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

13904번: 과제

 

문제를 간단히 정리하면 과제를 최대한 미루면서 가장 높은 점수를 받기이다. 즉, 마감일이 4일 남았으면 1, 2, 3일 남은 과제들을 하는 것이 이득이다. 4일 남은 과제의 점수가 제일 높다고 해서 1일차에 4일 남은 과제를 해버리면 1일 남은 과제의 점수를 날리게 된다. 어차피 모든 과제는 하루가 소요되기 때문에 마감일과 점수만 판단하면 된다.

 

내가 처음에 시도한 방법은 아래와 같다.

(잘못된 방법)
점수 내림차순으로 정렬한 뒤 0번 인덱스의 점수부터 더해준다.
이때 다른 과제들의 마감일을 1씩 차감하고, 만약 마감일이 -1인 과제가 있다면 리스트에서 삭제한다.

 

위처럼 하면 틀린다. 점수만 보고 판단할 경우 그 전에 제출할 수 있는 다른 과제들을 놓치기 때문이다. 이거는 큰 떡 1개 먹겠다고 작은 떡 1394819384개 잃는 셈이다. 때문에 점수만 보고 무작정 가져가면 안 된다.

 

 

해결 과정은 아래와 같다.

• 마감 기한과 점수를 이차원 배열로 입력받는다.
• 점수 기준 내림차순으로 정렬한다.
• 과제 수만큼 반복문을 돌린다. 이때 6일차에서 1일차 순으로 돌린다.
• 현재 정렬되어 있는 상태이기 때문에 제출할 수 있는 과제들 중 가장 높은 점수인 것을 찾는다.
• 6일차는 [6, 5]만 가능하다.
• 5일차는 없다.
• 4일차는 [4, 60], [4, 40], [4, 10] 중 60점이 가장 높다.
• 3일차는 [4, 40], [3, 30], [4, 10] 중 40점이 가장 높다. [4, 40], [4, 10]이  있는 이유는 3일차에 해도 되기 때문이다.
• 2일차는 [2, 50], [3, 30], [4, 10] 중 50점이 가장 높다.
• 1일차는 [3, 30], [1, 20], [4, 10] 중 30점이 가장 높다.
• 5 + 60 + 40 + 50 + 30 = 185

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

homework = []
result = [0] * 1000

for i in range(n):
    day, score = map(int, input().split())
    homework.append([day, score])

homework.sort(key=lambda x:-x[1])

for i in range(n):
    for j in range(homework[i][0]-1, -1, -1):
        if result[j] == 0:
            result[j] = homework[i][1]
            break

print(sum(result))