14501: 퇴사

• 역순으로 dp table 채워야함
• i가 N-1부터 0까지 순회할 때,
• 스케줄상 아예 일을 할 수 없는 경우
• • T[i] + i > N인 경우임. 이 경우는 dp[i]를 dp[i+1]로 채워줘야함 (뒷부분 날짜인 경우 0으로 채워주기 위해 dp를 N+1만큼 0으로 초기화해줌)
• 일을 할 수 있는 경우 최댓값을 찾아야함
• • T[i] + i <= N인 경우임. dp[i] = max(dp[i+1], P[i] + dp[T[i]+i])의 점화식을 이용해야함

N = int(input())
T = []; P = []
for i in range(N):
    tmp = list(map(int, input().split(' ')))
    T.append(tmp[0]); P.append(tmp[1])

dp = [0 for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    if T[i] + i <= N:
        dp[i] = max(dp[i + 1], P[i] + dp[T[i] + i])
    else:
        dp[i] = dp[i + 1]

print(dp[0])

• dp table 예시 1
  
• dp table 예시 2
  
• dp table 예시 3
  
• dp table 예시 4