백준 14501 퇴사

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

dp에 관한 문제이다.
dp는 항상 설계를 어떻게 잘 하느냐가 중요한 것 같다.

특정 날짜에 일을 하는게 맞는지를 판단하기 위해 dp를 사용하였다.

x일날 y기간동안 일을 한다면,
x일날 일의양 + y일 이후로 가능한 최대 일의양과 x일 다음날과 비교를 통해 x일에 일을 해야하는지 안해야 하는지 구분할 수 있다.

n = int(input())
t = []
p = []
for i in range(n):
    a,b = list(map(int,input().split()))
    t.append(a)
    p.append(b)
dp = [0 for i in range(n)]
dp.append(0)

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

print(dp[0])