[JAVA/DP] 백준 14501 퇴사

1. 문제

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

14501번: 퇴사

 

2. 풀이

• n일에 받을 수 있는 최대 수익을 기억하기 위해 DP 배열을 사용한다.
• 날짜 범위 내에 일 종료가 가능한 경우(i + time[i] <= n)
  • 일이 종료한 날짜에 벌게되는 금액의 최댓값을 구해 DP 배열에 저장한다 (Math.max(dp[i + time[i]], dp[i] + money[i]))
• 해당 날짜가 가능하지 않은 경우, 이전 날짜까지의 값이 최대이도록 처리한다. (dp[i+1] = Math.max(dp[i+1], dp[i]);)

 

3. 코드

 

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


class Main{
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] time = new int[n];
        int[] money = new int[n];
        
        for(int i = 0; i < n; i++){
            String[] input = br.readLine().split(" ");
            time[i] = Integer.parseInt(input[0]);
            money[i] = Integer.parseInt(input[1]);
        }
        
        // n일에 받을 수 있는 최대 수익
        int[] dp = new int[n+1];
        int max = 0;
        for(int i = 0; i < n; i++){
            if(i + time[i] <= n){ // 날짜 범위내에 일 종료가 가능한 경우
                dp[i + time[i]] = Math.max(dp[i + time[i]], dp[i] + money[i]);
            }
            // 해당 날짜가 가능하지 않은 경우
            // 이전 날짜까지의 값이 최대
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        
        System.out.println(dp[n]);
    }
}