백준 14501 퇴사 문제 간단 풀이

n = int(input())
t = [] #상담 완료하는데 걸리는 시간만
p = [] #상담 완료 했을 때 받는 금액
dp = [0]*(n+1)  #dp[i] = i일부터 퇴사 날까지 얻을 수 있는 최대 이익
max_value = 0

for _ in range(n):
    x,y = map(int, input().split())
    t.append(x)
    p.append(y)

for i in range(n-1, -1,-1):
    time = t[i]+i    #i번째 날이 상담 가능한 날짜 범위에서 넘어가는지 확인, time -> i번째날 상담 완료하는데 걸리는 시간 + i번째날
                    

    if time <= n:    #넘어가지 않을 경우
        dp[i] = max(p[i] +dp[time], max_value)  #현재 상담 일자의 이윤(p[i])+ 현재 상담을 마친 일자부터 최대이윤(dp[t[i]+i]) 계산해서 최댓값 저장
                                                #i번째 날부터 퇴사날(n)까지 얻을 수 있는 
        max_value = dp[i]
    else:               #넘어가는경우
        dp[i] = max_value #현재까지의 최대 금액 유지
print(max_value)