[백준_14501] 퇴사 python

dp를 거꾸로 뒤집어서 생각할 수도 있어야 한다는 교훈을 얻게 해 준 문제였다.

처음에 갈피를 잘못 잡아 애를 먹다가

구글링을 통해 아이디어를 얻었다.

역시 아직 멀었다.

# n 입력
n = int(input())

# t, p 설계
t = []
p = []

# a, b 입력
for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

# dp 설계
dp = [
    0 for _ in range(n+1)
]

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

# 출력
print(dp[0])