백준 15486 퇴사 2 자바(java)

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

15486번: 퇴사 2

 

풀이 방법

다이나믹 프로그래밍 문제이다.

결국 N일이 모두 지난 후의 최대 수익을 구해주면 되므로 dp에 저장되는 값을 해당 날까지의 최대 수익으로 설정하여 갱신시켜나가면 되겠다고 생각했다.

 

따라서, 오늘이 i일이라고 할 때

dp[i] = i일까지 가장 많이 벌 수 있는 경우의 최대 수익이다.

dp 배열은 N+2 크기로 생성한다. 이유는 N일까지 상담을 진행한 것은 N+1일에 금액을 받으므로  dp[N+1] 에 최대 수익을 저장해주기 위함이다!!!

 

1일부터 N일까지 보면서 dp 값을 갱신한다.

먼저, 지금까지의 최대 수익을 저장해주기 위해 dp[i] = max(dp[i], dp[i-1])을 하여 최대 수익을 누적시켜준다. 그 다음, i+t가 N+1을 넘지 않는다면 i일의 상담을 진행할 수 있으므로 dp[i+t] = max(dp[i] + t, dp[i+t]) 로 값을 비교하여 i+t일까지의 최대 수익을 갱신해준다. 

 

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][2];

        for(int i=1; i<=N; i++) {
            String[] line = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(line[0]);
            arr[i][1] = Integer.parseInt(line[1]);
        }

        int[] dp = new int[N+2];
        for(int i=1; i<=N; i++) {
            int t = arr[i][0];
            int p = arr[i][1];
            dp[i] = Math.max(dp[i], dp[i-1]); // 지금까지의 최대 수익 갱신
            if(i+t <= N+1) { // i일의 상담을 하고 난 후인 i+t일의 최대 수익 갱신
                dp[i+t] = Math.max(dp[i] + p, dp[i+t]); 
            }
        }
        System.out.println(Math.max(dp[N], dp[N+1]));
    }
}