백준 15486번 퇴사2 (JAVA)

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

15486번: 퇴사 2

 

저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다.

DP를 통해 해당 일자까지 오는데 최대 금액을 저장하도록 하였습니다.

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15486 {
    private static class Work{
        int day;
        int pay;

        public Work(int day, int pay) {
            this.day = day;
            this.pay = pay;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        Work input[] = new Work[n];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int day = stoi.apply(st.nextToken());
            int pay = stoi.apply(st.nextToken());
            input[i] = new Work(day,pay);
        }
        int dp[] = new int[n+1];
        int max = 0;
        for(int i = 0 ; i < n ; i++){
            Work work = input[i];
            max = Math.max(max,dp[i]);
            dp[i] = max;
            if(work.day + i  <= n){
                dp[work.day + i] = Math.max(dp[work.day + i], max + work.pay);
            }
//            System.out.println(Arrays.toString(dp));
        }
//        Arrays.fill(dp,-1);
//        System.out.println(dfs(n,input,0,dp));
        int result = Math.max(dp[n-1],dp[n]);
        System.out.println(result);
    }
}