> 문제 <

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

> 아이디어 <

다이나믹 프로그래밍 이용

Dynamic Programming?

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법
작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생긴다.
그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍

뒤에서부터 차근차근 풀어나가야한다!
1. 현재 날의 이윤 + 현재 날로부터 필요한 날 뒤의 이윤 (ex. 1일차 이윤 + 4일차 이윤)
2. 현재 날을 건너뛰고 다음날의 이윤 (i+1의 이윤)
1과 2 중 큰 값이 최대 이윤이 된다.
---> dp[i] = max(p[i] + dp[i + t[i]], dp[i+1])

> 코드 <

n=int(input())
t=[]
p=[]
dp=[]
for i in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)
    dp.append(b)
dp.append(0)
for i in range(n-1,-1,-1):
    if t[i]+i > n:
        dp[i]=dp[i+1]   # 0으로
    else:
        dp[i]=max(p[i]+dp[i+t[i]], dp[i+1])  # 현재날이윤+다음이윤과 뒤에서부터 합해온 페이들 중에 max값 찾기
print(dp[0])

> 📃🖋 <

클론 코딩.
궁금한 점이 13번째 줄 dp[i]=dp[i+1] 을 dp[i]=0으로 표현해도 되는게 아닌가? 싶은데
틀렸다고 나온다. 왜일까...

클론코딩 출처 : https://pacific-ocean.tistory.com/199

파이썬 코드 시각화 : http://pythontutor.com/visualize.html#mode=edit