[JAVA] 백준 14501번- 퇴사

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

14501번: 퇴사

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] T = new int[n+1];
        int[] P = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());

            dp[i] = P[i];
        }

        for(int i=2; i<=n; i++){
            for(int j=1; j<i; j++) {
                if(i-j < T[j]) continue;
                dp[i] = Math.max(dp[i], dp[j] + P[i]);
            }
        }

        int max=0;
        for(int i=1; i<=n; i++){
            if(i + T[i] > n+1) continue;
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}