[백준] 13904 - 과제

1. 문제

13904번: 과제

2. 개요

그리디? 문제

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())

assignments = []
maxdays = 0
ans = 0

for i in range(N):
    d, w = map(int, sys.stdin.readline().split())
    maxdays = max(maxdays, d)
    assignments.append([d, w])

assignments.sort(key = lambda x : x[-1])
sched = [0 for i in range(maxdays)]

for a in assignments[::-1]:
    for i in range(a[0]-1, -1, -1):
        if sched[i] < a[1]:
            sched[i] = a[1]
            ans += a[1]
            break
        
print(ans)

일단 과제의 최종 제출일자를 구하고 일정 리스트를 판다.

제출기한이 있는 과제들의 점수의 최댓값을 구하는 문제이므로 점수순으로 정렬한다.

점수가 높은 과제들부터 순차적으로 돌면서 해당 과제의 최종 제출일자부터 역으로 일정을 돈다.

만약 해당 일정이 빈 일정이라면 그 일자에 과제를 넣고 나온다.

점수가 높은 순으로 탐색했기 때문에 점수가 더 낮은 일자를 찾을 일은 사실 없다.