문제

https://www.acmicpc.net/problem/14501

나의 코드 (답안 참조)

"""
1. 아이디어
마지막 날부터 최선의 경우를 DP로 계산해준다.

2. 시간복잡도
O(2N) 정도?
"""

"""
일하는 날을 맨 뒤에서부터 계산해보자
7일을 선택하면 근무시간 초과로 이익 0
6일도 마찬가지
5일을 선택하면 이익 15
4일을 선택하면 이익은 20에, 5일에도 일할 수 있으므로 +15 해서 35
3일을 선택하면 이익은 10에 4일에도 일할 수 있으므로 (4일에 일하면 위에서 확인했듯이 5일도 일한다) +35 이므로 45
2일을 선택하면 이익은 20
1일을 선택하면 이익은 10에 4일부터 일할 수 있으므로 ( 아까 그 35 를 더한다) +35 이므로 45

결과적으로 1,4,5 일하면 45
또는 3,4,5 일하면 45
이 두가지의 경우가 최대이다.
"""

from sys import stdin
input = stdin.readline

n = int(input())
profit = [ list(map(int, input().split())) for _ in range(n) ]
dp = [0] * (n+1)

for i in range(n-1, -1, -1):
    if profit[i][0] + i > n: # 근무시간을 초과한 경우
        dp[i] = dp[i+1] # 현재 일을 하지 않는다
    else:
        # max(현재 일을 끝내고 현재 일을 끝낸 날에 쌓여있는 보상, 현재 일을 하지 않는 경우)
        dp[i] = max(profit[i][1] + dp[i + profit[i][0]], dp[i+1])

print(dp[0])

    

느낀점

주석을 최대한 상세하게 쓰긴 썼는데 이해하는데 굉장히 오래 걸렸다.
일반 dp문제와는 다르게 뒤에서 부터 세어야 한다는 것을 생각하기 힘들었다.
여러번 풀어볼 필요가 있다.