[알고리즘][백준] 15486. 퇴사

문제

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

 

문제 아이디어

1	2	3	4	5	6	7
3	5	1	1	2	4	2
10	20	10	20	15	40	200

 

차근차근 생각해봅시다.

1일차: 상담을 하면 3일차에 끝나게 됩니다. 그러면 4일차부터는 10의 비용이 더해지게 됩니다.

2일차: 상담을 하면 7일차에 끝나게 되고, 7일차에 20의 비용을 더해줍니다.

3일차: 상담을 하면 3일차에 끝나고, 3일차에 10의 비용을 더합니다. 

4일차: 상담을 하면 4일차에 끝나고, 4일차에 20의 비용을 더하는데, 여기서 1일차에 끝난 비용을 더해준다면 총 30의 비용입니다. (혹은 3일차에 끝난 비용을 더해도 됩니다.)

* 즉 이전 날짜까지 총 상담 기록을 봤을 때를 더해주는 느낌입니다.

5일차: 상담은 7일차에 끝나고, 4일차까지의 기록을 보면 5일차도 총 30까지의 비용이 듭니다. (물론 5일차 상담은 아직 안 끝났습니다.)

6일차: 상담은 7일차를 넘어가서 상담이 불가능합니다. 비용은 1 -> 4로 전달 받은 30의 비용이 듭니다.

7일차: 1 (3) -> 4 -> 5로부터 전달 받은 10 + 20 + 15 = 45 비용이 듭니다.  

 

즉, 이전 날짜까지 총 얼마의 비용을 들여서 상담을 했는지 보고, 해당 날짜 기준 소요 시간 직전까지 총 얼마의 비용이 드는지 계산해줍니다. 2일차를 기준으로 생각했을 때, 2일차 상담은 7일차에 끝나므로 1일차까지 든 비용 (dp[1]) 에 2일차 비용 (value = 20) 을 더한 값을 dp[7] 에 업데이트합니다. 물론 dp[7]을 업데이트하는 다른 날짜들이 있을 수 있으므로 (ex. 5일차) 최댓값으로 업데이트해줘야 합니다. dp[i + cost - 1] =  (max(dp[i - 1] + value, dp[i + cost - 1])

 

import sys
input = sys.stdin.readline

N = int(input())
cons = [0 for _ in range(1600000)]
val = [0 for _ in range(1600000)]
dp = [0 for _ in range(1600000)]

for i in range(1, N + 1):
    cost, value = list(map(int, input().split(' ')))
    dp[i] = max(dp[i - 1], dp[i])
    if i + cost - 1 <= N:
        dp[i + cost - 1] = max(value + dp[i - 1], dp[i + cost - 1])


print(max(dp))