[백준] 14501번 퇴사 (python)

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

---

 

보자마자 DP인건 알아챘는데 점화식 세우는데 오래 걸렸다..

문제 예제를 보면 6, 7일 같은 경우 N을 벗어나기 때문에 포함시킬 수 없다. 이 조건을 보고 역순으로 풀어야겠다고 판단했다. (근데 앞에서부터 풀어도 된다.)

 

뒤에서부터 오는데 만약 인덱스 + time이 N을 넘어가면 dp[i] = dp[i+1]을 해주었다.

처음에는 dp[i] = 0을 했는데, 이렇게 되면 time이 1일 때도 0으로 되기 때문에 틀린다.

 

ex) n = 7일 때,

만약 6일에 하는 미팅이 이틀 걸리면 퇴사 날짜를 넘기기 때문에 못한다. 근데 7일에 하는 미팅이 하루 걸리는 거면 포함시켜야 한다. 이를 포함시키는 코드가 아래와 같다.

이 코드를 처음에는 dp[i] = 0으로 구현했다가 포함시킬 수 있는 미팅까지 없애버려서 최대 이득이 안 나왔다..

 

그 이후에는 점화식을 작성해서 풀면 된다. 그날 미팅하고 이후 미팅을 하는 게 이득인지, 아니면 앞에서 더해온 dp 값이 이득인지 판단했다.

dp[i+schedules[i][0]]은 미팅 소요 날짜를 더해준 거다. 만약 첫 번째 미팅을 했는데 3일 걸린다면 3일 후인 네 번째 미팅을 더해준 거다.

이때 schedules[i]의 0번째 인덱스는 소요 시간이고, 1번째 인덱스는 돈이다.

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
schedules = []
for _ in range(n):
    time, money = map(int, input().split())
    schedules.append([time, money])

dp = [0 for _ in range(n+1)]

for i in range(n-1, -1, -1):
    if i + schedules[i][0] > n:
        dp[i] = dp[i+1]
    
    else:
        dp[i] = max(dp[i+1], schedules[i][1] + dp[i+schedules[i][0]])
    
print(dp[0])