[DP] 14501번 - 퇴사(36일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#상담 가능 날짜
n = int(input())
#상담 소요 시간, 비용 입력을 위한 list
T, P = [0 for i in range(n+1)], [0 for i in range(n+1)]
#상담 소요 시간, 비용 입력
for i in range(n):
    a,b = map(int, input().split())
    T[i] = a
    P[i] = b

#i번째날까지 일을 했을 때의 최대값을 저장하는 dp 선언
dp =[0 for i in range(n+1)]

#순차 탐색보다 역순 탐색이 효율적 (n -> 0까지 탐색)
for i in range(len(T)-2, -1, -1): 
    #날짜를 초과하지 않은 경우
    #해당 날짜를 건너뛰는 경우와, 해당 날짜에 상담을 하는 경우 중 비용이 큰 값을 dp에 저장
    if (T[i]+i <= n):      
        dp[i] = max(P[i] + dp[i + T[i]], dp[i+1])   
    #날짜를 초과한 경우
    #해당 날짜에 상담을 할 수 없으므로 건너뜀
    else:                 
        dp[i] = dp[i+1]
#모든 탐색이 완료된 뒤 최대값이 저장된 dp[0] 출력
print(dp[0])

#인사이트
#유형 분석 실패
#dp일 것 같다고 생각했지만 브루트포스 탐색 문제라 dfs로 풀어야 할 것 같다고 착각함
#문제 유형에 얽매이지 않는 유연한 사고가 필요함