[백준] 15486번 퇴사2 (Java)

백준 15486 퇴사2

N의 숫자가 상당히 큰 것을 미루어 보아 완전 탐색은 아니라고 추측할 수 있다.

1. 완전 탐색은 아니다.
2. 앞에 일어난 사건이 뒤에 일어난 사건에 영향을 준다.
3. 하지만 뒤에서 일어난 사건이 앞에 일어난 사건에 영향을 주진 않는다.

즉, DP로 해결해야한다는 것을 알 수 있다. 조심해야할 점이 있었다. 하루가 걸리는 일은 당일에 일을 끝내고 수당을 챙길 수 있다. 일을 시작할 수 있는 날을 기준으로 수당을 저장하면 마지막 날에 당일 하루만 일하고 수당을 받는 날은 계산이 되지 않는다. 수당을 받는 날을 기준으로 DP를 활용하되, 최대값을 기억하는 변수를 만든다면 해결할 수 있다.

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

public class Main {
     public static class Pair{
         int t, p;
        public Pair(int a, int b){
             this.t = a;
             this.p = b;
        }
    }

    public static void main(String[] args) {
        try {
            int n, a, b, tmpDate, maxV = 0;
            int [] dp;
            Pair [] table;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
            n = Integer.parseInt(br.readLine());
            dp = new int[n + 1];
            table = new Pair[n + 1];
            for(int i = 1; i <= n; i ++){
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                Pair p = new Pair(a - 1, b);
                table[i] = p;
            }
            for(int i = 1; i <= n; i ++){
                tmpDate = i + table[i].t;
                if(tmpDate <= n){
                    dp[tmpDate] = Math.max(dp[tmpDate], maxV + table[i].p);
                }
                maxV = Math.max(maxV, dp[i]);
            }
            System.out.println(maxV);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}