[백준] 퇴사2 15486 java - dp

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

 

dp에 대한 연습이 많이 필요하겠다...

일단 범위를 봐서는 완탐으로 풀면 시간초과가 날 것

매일의 이익을 dp 배열로 두고 풀어야 한다 !!

 

import java.io.*;
import java.util.*;

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+2];
        int[] P = new int[N+2];
        int[] dp = new int[N+2];
        int max = Integer.MIN_VALUE;

        StringTokenizer st = null;

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

        for(int i=1;i<=N+1;i++){
            max = Math.max(max, dp[i]);

            int next = i+T[i];

            if(next<N+2){
                dp[next] = Math.max(max+P[i], dp[next]);
            }
        }
        System.out.println(max);

    }

}