백준(14501): 퇴사(python)

출처| https://www.acmicpc.net/problem/9663

N = int(input())
T = []
P = []
DP = [0 for i in range(N+1)]

for _ in range(N):
    T_i,P_i = map(int, input().split())
    T.append(T_i)
    P.append(P_i)
    
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], DP[T[i]+i]+P[i])
        
print(DP[0])

분명 완전탐색 카테고리에 있는 문제였는데 어떻게 풀어야할지 감이 안와서 구글링해보니까 DP로 다들 푸셔서
DP 공부도 해볼 겸 참고했다. 일단 풀이를 보고 이해하는 것부터가 힘들었다.

뒤에서부터 dp를 풀면 된다. 크게 두 가지 경우가 있다.

1. 상담에 필요한 일 수가 퇴사일을 넘어가는 경우
   -> 해당 일자에 일을 할 수 없으니 다음날의 dp 값을 그대로 가져온다. (dp의 최댓값인 dp[i+1])

2. 퇴사일을 넘어가지 않을 경우
   (i) 오늘 상담을 하지 않을 경우 : dp[i+1] (지난 상담까지의 보수)
   (ii) 오늘 상담을 할 경우 : dp[t[i] + i] + p[i] (dp[오늘 날짜 + 오늘 시작할 상담에 필요한 일 수] + (상담 보수))