백준 15486. 퇴사 2 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/15486

"DP"

다시 보기.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int[][] map;
    static int[] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        map = new int [n+2][2];
        dp = new int [n+2];
        
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
        }
        
        int max = 0;
        
        for (int i = 1; i <= n+1; i++) {
            max = Math.max(max, dp[i]);
            
            int day = map[i][0];
            int pay = map[i][1];
            
            if(i + day > n + 1) 
                continue;
            
            dp[i+day] = Math.max(max + pay, dp[i + day]);
        }
        System.out.println(max);
    }
}