[알고리즘_풀이] 백준 14501번, 퇴사. DP

전형적인 dp문제 중, 최댓값(Math.max) 구하는 것. 

bottom-up,

저장해놓은 것보다 큰 값이면 ok아니면 새로 계산한 값 넣기의 종류

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();    // 상담 가능 일자
        int[] T = new int[N+10]; // 상담을 완료하는데 걸리는 일자
        int[] P = new int[N+10]; // 상담을 했을 때 받을 수 있는 돈
        int[] dp = new int[N+10];// dp memoization을 위한 배열

        //1부터 N까지 입력받는다.
        for(int i=1; i<=N; i++){
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

        int max = 0; // i일 이전까지의 최대로 받을 수 있는 값

        // 돈은 일을 끝마친 다음날에 입금된다고 생각하면 된다. 따라서 N+1(퇴사일)이 됐을 때, 얼마 받는지가 최대금액
        for(int i=1; i<=N+1; i++){
            // i일 이전까지의 최댓값과 자기자신 중 큰 값.
            dp[i] = Math.max(max, dp[i]);

            // i일에 상담했을 때, 받을 수 있는 돈은 i+T[i]인 상담이 다 끝난 후에 받는다. 따라서 이때를 계산해주는 부분
            if(i+T[i] <= N+1){
                dp[i+T[i]] = Math.max(dp[i+T[i]], dp[i] + P[i]);
            }

            // i까지 했을 때 최댓값 구하는 부분. 이제 i+1로 넘어가기전, 최댓값을 담아주고 다음 루프에서 이전까지의 최댓값으로서 쓰인다. 
            // 루프가 끝난다면 어쨌든 마지막 날까지의 최댓값이기 때문에 정답으로 출력해주면 된다.
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);
    }
}

 

 

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

14501번: 퇴사