[Python3] 백준(Baekjoon) 과제 13904

 

문제 :

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

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

 

접근 :

처음 접근 방법은 마감 짧은 것, 점수 높은 것 순서로 정렬하여, 짧은 것 중 점수가 높은 것 선별 후에 문제를 풀어야겠다고 생각했다.

score.sort(key=lambda x: (x[0], -x[1])) 방식으로 정렬을 했는데, 다음날이 마감인 것 중 2순위가 오늘 처리할 것 보다 점수가 높은 경우에 대해서 예외처리를 해줄 수 없어서 실패했다.

그 다음 접근으로는 [0] * 1001짜리 빈 배열을 만들고, 마감 날짜에 딱 맞춰서 문제를 푸는 형식으로 구현했지만 실패했다.

결국, 위의 접근을 조금 변형해서, 점수가 높은 것을 기준으로 정렬하고, 리스트의 앞에서부터 과제를 낼 날짜를 탐색하고 최대한 마감 날짜에 맞추되, 날짜를 조정해서 점수가 높은 것부터 처리하는 방식으로 했다.

 

풀이 :

import sys
input = sys.stdin.readline

n = int(input())
score = [list(map(int, input().split())) for _ in range(n)]
score.sort(key=lambda x: x[1], reverse=True)
date = [0] * 1001

for day, worth in score:
    i = day
    #마감 기한이 끝나지 않았으면서, 가장 늦은 마감날을 찾는 방법
    while i > 0 and date[i] != 0:
        i -= 1
    #과제를 할 시간이 없을 경우
    if i == 0:
        continue
    #마감 날을 찾은 경우
    else:
        date[i] = worth
print(sum(date))