이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 메모라이제이션을 위한 dp배열을 만들고 점화식을 구하였다. 점화식을 구해보면 dp[i+t[i]]=dp[i]+p[i], dp[i]=dp[i-1] 이렇게 두가지로 나타난다. 이 두가지 방법을 통해 더 큰 값을 dp[i]로 취하면 문제를 해결할 수 있다. 계속해서 시간초과가 발생하여서 질문란을 보니 이 문제의 경우 입력이 너무 많아 입력 시 그냥 input을 사용하면 시간초과가 발생하는 것으로 보였다. 그래서 sys.stdin.readline()을 통해 입력하였다.

• n을 입력받는다.
• t, p배열을 0 하나씩 채워서 선언한다. (인덱스 1부터 사용하기 위함)
• dp배열을 0 n+2개로 채운다.
• n만큼 반복하는 for문을 돌린다.
  -> a, b를 입력받고 t에 a를, p에 b를 넣는다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[i]를 dp[i]와 dp[i-1] 중 더 큰 값으로 갱신한다.
  -> 만약 i+t[i]가 n+1보다 작거나 같은 경우 dp[i+t[i]]를 dp[i+t[i]]와 dp[i]+p[i] 중 더 큰값으로 갱신한다.
• dp에서 가장 큰 수를 출력한다.

Code

import sys
n=int(sys.stdin.readline().rstrip())
t=[0]
p=[0]
dp=[0]*(n+2)
for _ in range(n):
    a, b=map(int, sys.stdin.readline().split())
    t.append(a)
    p.append(b)
for i in range(1, n+1):
    dp[i]=max(dp[i-1], dp[i])
    if i+t[i]<=n+1:
        dp[i+t[i]]=max(dp[i+t[i]], dp[i]+p[i])
print(max(dp))