# 퇴사 2 import sys input = sys.stdin.readline def solution(): n = int(input().rstrip()) t = [0] * (n+1) p = [0] * (n+1) for i in range(1, n+1): t[i], p[i] = map(int, input().rstrip().split()) dp = [0] * (n+2) max_p = 0 for i in range(1, n+1): max_p = max(max_p, dp[i]) nxt = i+t[i] if nxt <= n+1: dp[nxt] = max(dp[nxt], max_p+p[i]) print(max(max_p, dp[n+1])) return solution() """ 걸린 시간: 몰라 시간 복잡도: 과거에서 미래 한 시점에만 업데이트를 하기 때문에 n 테이블을 다 채우기만 하면 되므로 O(n)이다. 해설: 14501(퇴사)번 문제는 n이 작았기 때문에 dp[i]를 채울 때 이전 값들 중에 i로 올 수 있는 것들을 전부 보고 최대값을 구하는 O(n^2)로 해도 괜찮았다. 근데 이번 문제는 n이 많이 크기 때문에 기존 방식은 안된다. 따라서 미래에서 과거를 보는 것이 아닌 과거에서 미래로 값을 놓는 방식을 선택했다.(답 보고 알았음) i를 볼 때 지금까지의 최대 수익을 계속 기록해놓으면서 i에서 상담을 했다고 쳤을 때, 상담이 끝나는 날(nxt)에 i에 상담을 한 경우(max_p + p[i])와 더 과거에서 온 이력(dp[nxt])중 최대를 비교해서 갱신한다. 이렇게 기록해놓으면 미래에는 과거에서 이 미래까지 온 최선의 경우의 수를 이미 가지고 있고, 이것과 별개로 여기서 상담을 하지 않았을 때 최대 수익도 가지고 있다. 이 둘을 계속 비교해가며 최대 수익을 갱신하고, 마지막에는 n+1날까지 온 최선의 수와 전체 최대 수익을 비교하여 마무리 한다. max_p = max(max_p, dp[n+1])은 하지 않았었기 때문. """