https://www.acmicpc.net/problem/14501
n = int(input())
lis = []
for i in range(n):
t, p = map(int, input().split())
lis.append((t, p))
dp = [0]*(n+1)
for i in range(n-1, -1, -1):
t, p = lis[i]
if i+t > n:
dp[i] = dp[i+1]
else:
dp[i] = max(dp[i+1], p+dp[i+t])
print(dp[0])
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n,m;
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer((bf.readLine()));
int n=Integer.parseInt(st.nextToken());
int[][] tp=new int[2][n];
int[] dp=new int[n+1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(bf.readLine());
tp[0][i] = Integer.parseInt(st.nextToken());
tp[1][i] = Integer.parseInt(st.nextToken());
}
for(int i=n-1;i>=0;i--){
int t=tp[0][i];
int p=tp[1][i];
if(i+t>n) dp[i]=dp[i+1];
else dp[i]=Math.max(dp[i+1],p+dp[i+t]);
}
System.out.println(dp[0]);
}
}
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <math.h>
#include <numeric>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n+1, 0);
vector<vector<int>> input(n,vector<int>(2));
for (int i = 0; i < n; i++) {
cin >> input[i][0];
cin >> input[i][1];
}
if (input[n - 1][0] == 1)dp[n - 1] = input[n - 1][1];
for (int i = n-2; i >=0; i--) {
if (input[i][0] + i > n) {
dp[i] = dp[i + 1];
continue;
}
dp[i] = max(dp[input[i][0] + i] + input[i][1],dp[i+1]);
}
cout << dp[0];
}
퇴사날부터 역으로 얻을 수 있는 최대의 수익을 dp 테이블에 저장했습니다