백준 14501 파이썬(DP)

DP문제로 

이 문제는 뒤에서부터 생각해야 풀 수 있다.

뒤에서 풀어보려고 계속 노력하다가 결국엔 다른 사람의 블로그를 참고해서 풀었다.

참고 블로그 https://pacific-ocean.tistory.com/199

 

# 14501번: 퇴사
n = int(input())

t_list = []
p_list = []
for _ in range(n):
    t,p = map(int,input().split())
    t_list.append(t)
    p_list.append(p)

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

print(dp[0])