백준 알고리즘 파이썬(Python) 14501번 퇴사

---

뒤에서부터 채워나가는 DP(다이내믹 프로그래밍) 문제이다.

 

 

 

출처 : https://pacific-ocean.tistory.com/199

 

 

 

우선 백준이는 N+1번째 날에는 퇴사를 하기 때문에 ' intex + T(i) ' 값이 N(여기서는 7)을 넘어갈 수 없다.

예를 들어 7일째를 보면 index가 6이고 T(i) 값은 2이므로 6+2의 값이 7을 넘어가게 된다.

마찬 가지로 6일째도 index가 5이고 T(i)값은 4이므로 5+4의 값은 7을 넘어가게 된다.

이럴 경우에는 아까 말했다 싶이 뒤에서부터 채워나가는 DP이므로 i+1번째 있는 DP값을 그대로 내려받는다.

따라서 dp[6]과 dp [5]는 차례로 0이 된다.

 

 

이제 5일째 즉 index가 4인 경우의 날을 보면 index가 4이고 T(i) 값은 2이므로 4+2는 7을 넘어가지 않는다.

이때부터는 그 위의 dp값 즉 여기서는 ' dp [5]의 값 '과 index가 4인 날의 ' P(4) + dp(4 + T(4)) ' 중 큰 값을 가져오면 된다.

 

 

즉 점화식은 dp[i] = max(dp [i+1], array_p [i] + dp [i + array_t [i]]) 

(여기서 array_p 가 P, array_t 가 T를 의미한다)

 

 

 

예를 들어 i가 4라고 한다면,

 

dp[i + 1]의 값 -> (0)과 p [i] + dp [i + t [i]] -> (15 + 0)의 값 중 큰 값을 넣어준다.(dp [4] = 15)

 

i가 3이라고 했을때,

 

dp [i + 1]의 값 -> (15)와 p[i] + dp[i + t [i]] -> (20 + 15)의 값 중 큰 값을 넣어준다.(dp [3] = 35)

 

이런 식으로 최댓값을 넣어주면 i가 0일 때 최댓값이 되므로

 

dp [0]의 값을 출력해준다.

 

 

n = int(input())
array_t = []
array_p = []
dp = [0] * (n+1)
for i in range(n):
    t, p = map(int,input().split())
    array_t.append(t)
    array_p.append(p)
    
for i in range(n-1, -1, -1): # n-1에서 시작해서 0까지 -1씩 빼준다.
    if array_t[i] + i > n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], array_p[i] + dp[i + array_t[i]])
        
print(dp[0])