퇴사

• 퇴사 2의 쉬운 버전. 이 문제에서는 N이 워낙 작아서 브루트포스로도 풀리긴 한다.
• 정해는 DP로 푸는 것. 하지만 DP[i] 를 i일째 받을수 있는 최대 금액이라고 놓았을때, i에 대해서 이러테이션하면서 DP[i]를 DP[j](j<i) 들을 이용해서 계산하는 것은 잘 안된다. DP[i] = max(DP[i-1], max_j(DP[j] + P_j) if j + T_j == i) 이런식인데, 모든 j에 대해서 j + T_j가 i가 되는지를 찾아서 처리하려면 총 시간복잡도가 O(n^2)이 된다. i에 대해서 이터레이션 하면서 DP[i+T_i] = max(DP[i+T_i], DP[i] + P_i) 와 같은 식으로 업데이트해주어야 O(n)에 계산 가능하다.
  • 어떻게 보면 각 i를 정점으로 하고 i에서 i+1과 i+T_i로 가는 엣지가 있는 그래프에서 (웨이트는 0과 P_i), 1에서 N까지 가는 최장경로를 구하는 것이라고 생각할수도 있다.

"""Solution code for "BOJ 14501. 퇴사".

- Problem link: https://www.acmicpc.net/problem/14501
- Solution link: http://www.teferi.net/ps/problems/boj/14501

Tags: [DP]
"""


def main():
    N = int(input())
    dp = [0] * (N + 5)
    for i in range(N):
        t_i, p_i = [int(x) for x in input().split()]
        dp[i + 1] = max(dp[i + 1], dp[i])
        dp[i + t_i] = max(dp[i + t_i], dp[i] + p_i)
    print(dp[N])


if __name__ == '__main__':
    main()