[백준/파이썬] 13904번 과제

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

13904번: 과제

점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다.

 

우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다.

해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다.

 

결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다!

(여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
arr=[]
cnt = -1
ans = 0

for i in range(n):
    d,w = map(int,input().split())
    arr.append([d,w])
    cnt = max(cnt,d)
    
arr = sorted(arr,key=lambda x:-x[1])
visited = [0 for _ in range(cnt+1)]

for day,weight in arr:
    if visited[day]==0:
        visited[day] = weight
    else:
        day-=1
        while day:
            if visited[day]==0:
                visited[day] = weight
                break
            day -= 1
            
for w in visited:
    ans += w

print(ans)