[BOJ] 백준 [15486] 퇴사 2 JAVA

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

15486번: 퇴사 2

📝문제

📝풀이

하루씩 순차적으로 진행하면서 특정 일의 상담을 진행하고 나서 받는 총 합 이익을 갱신 시켜주면 된다.
특정일을 i 
상담 걸리는 시간을 A(i)
페이를 P(i) 
페이 총합을 S(i) 라고 했을 때 점화식은
S(i + A(i)) = max( S(i + A(i)), S(i)+P(i) ) 가 된다. 

추가로)
i 의 범위는 i 번째 상담을 끝 났을 때 i+1 일에 정산 받는다는 걸 가정하여 n+1 까지.
해당 점화식은 상향식으로 하고 있기 때문에 기록한 최대 페이를 지나온 곳 까지 기록하기 위해 maxPay 를 계속 갱신. 

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

public class Main {


    static int n;
    static int[] dp;
    static Consult[] arr;

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

        n = Integer.parseInt(br.readLine());
        dp = new int[n+2];
        arr = new Consult[n+2];
        for(int i=1;i<=n;i++){
            arr[i] = new Consult(br.readLine());
        }
        arr[n+1] = new Consult("0 0");

        int maxPay = Integer.MIN_VALUE;
        for(int i=1;i<=n+1;i++){

            if(maxPay < dp[i]){
                maxPay = dp[i];
            }

            if(arr[i].days+i > n+1)
                continue;

            dp[arr[i].days+i] = Math.max(dp[arr[i].days+i],maxPay+arr[i].pays);
        }

        System.out.println(maxPay);
    }

    static class Consult{
        int days;
        int pays;

        public Consult(String in) {
            int[] input = Arrays.stream(in.split(" "))
                     .mapToInt(Integer::parseInt).toArray();
            this.days = input[0];
            this.pays = input[1];
        }
    }
}