[백준] 13904번 - 과제 (파이썬)

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

13904번: 과제

 

[코드]

import sys

N = int(sys.stdin.readline())
homeworks = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
homeworks.sort(reverse=True, key=lambda x: x[1])
schedule = [0] * (max(x[0] for x in homeworks) + 1)


for homework in homeworks:
    deadline = homework[0]
    if schedule[deadline] == 0:
        schedule[deadline] = homework[1]
    else:
        while deadline > 1:
            deadline -= 1
            if schedule[deadline] == 0:
                schedule[deadline] = homework[1]
                break

print(sum(schedule))

 

[설명]

맨처음에는 그날 그날 데드라인중 가장 점수가 높은 과제를 해나가는 형태로 풀었더니 틀렸다.

다음과 같이 풀어야한다.

 

schedule 배열을 생성한다.

점수가 높은 과제 순서대로 데드라인 날짜에 해당 과제를 할 것을 schedule에 적는다.

4번째 날에 60점과제 하기

schedule[4] = 60 

2번째 날에 50점과제 하기

schedule[2] = 50 

 

만약 그 날짜에 이미 다른 과제(더 높은 점수의)가 하기로 되어있다면 그전날짜에 해당과제를 배정한다. 

4번째 날에 40점 과제를 할려고 했는데, 이미 60점과제 스케쥴을 잡아놓았음. 따라서 3번째 날로 배정

schedule[3] = 40

 

이때, 1일까지 전부 스케쥴이 꽉차 있다면 해당과제는 포기한다.

schedule 배열의 모든 과제점수의 합을 구한다.