[그리디] Python - 13904번, 과제(시간복잡도 4등)

www.acmicpc.net/problem/13904

import sys
input = sys.stdin.readline

N = int(input())
homeworks = []
for _ in range(N):
    homeworks.append(list(map(int, input().split())))
homeworks.sort(reverse=True, key=lambda x: x[1])

score = 0
days = [0]*1001
for homework in homeworks:
    for d in range(homework[0], 0, -1):
        if days[d] == 0:
            days[d] = 1
            score += homework[1]
            break
print(score)

값을 입력 받고, 이것을 받는 점수를 기준으로 내림차순 정렬해준다.

그럼, 예시의 경우에는 다음과 같이 정렬된다.

 

4 60
4 40
1 20
2 50
3 30
4 10
6 5

 

여기서 for문으로 돌면서, 각각의 과제를 최대한 마감기한에 근접하도록 스케줄링하려고 하였다.(당연히 이렇게 해야하는 것이, 만약 위에서 '4 60'과 '4 40'의 경우가 우선순위가 가장 높다고 해서 각각 1, 2일에 배치를 하면 최악의 결과가 나온다.)

아무튼 의도하는 바는, '4 60'을 4일에, 그리고 '4 40'을 3일에 두는 식으로 한다는 것이다.

이를 위해서, 각 날짜에 할 일이 있는지를 확인하는 days를 두었고, homeworks를 따라 for문을 돌게 된다.

각 homework에선 (해당 과제의 데드라인)~1까지 반복문을 돌면서 그 날짜가 비어있으면 그 날에 해당 homework를 스케줄한다. '4 60'을 4일에 스케줄한 뒤, '4 40'의 경우에는 4~1까지 돌면서 비어있는 날을 체크하는 것이다.(3일에 스케줄된다.)