백준 boj 14501 - 퇴사 (파이썬, python)

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

14501번: 퇴사

 

다이나믹 프로그래밍을 통해 해결하였다.

다만, 문제를 풀면서 고려해야할 조건이 2가지인데, 최대값과 일자를 고려하여야 했다.

주어지는 일자를 넘어가면 안 되는데, 이를 위해 for문을 역순으로 돌렸다.

 

값을 구할 때에 뒤에서부터 더해질 수 있는 최대값을 구해나가고,

일자를 벗어난다면 전의 결과를 저장함으로써 0번째 인덱스에 최대값을 도출할 수 있게 했다.

 

code

 

total = int(input())
days =[]
cost = []
dp = []
for i in range(total):
    n, m = map(int, input().split())
    days.append(n)
    cost.append(m)
    dp.append(m)
dp.append(0)
for i in range(total - 1, -1, -1):
    if days[i] + i > total:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], cost[i] + dp[i + days[i]])
print(dp[0])