코딩테스트 준비/[백준]
[백준] 13904번 - 과제 (파이썬)
bled
2021. 5. 15. 21:38
https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
[코드]
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 배열의 모든 과제점수의 합을 구한다.