[BaekJoon] 15486번 퇴사2 (Java) 문제 풀이 [Gold 5]

문제

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

 

어떻게 풀 것인가?

주어진 날짜와 수익 배열을 통해서 최대 수익을 낼 수 있는 경우를 찾으면 되는 문제였다. 해당 문제는 Bottom-up 방식으로 1일부터 차례대로 최댓값을 갱신해주도록하면서 풀었다.

 

1일차 (N==1)

dp[1] = 0,  // 1일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 1 + T1 = 4 

dp[4] = Math.max( dp[4], dp[1] + P1) = 10 // 1일을 마치고 4일에 얻은 최대 금액 10 저장

 

 

2일차 (N==2)

dp[2] = 0,  // 2일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 2 + T2 = 7 

dp[7] = Math.max( dp[7], dp[2] + 20) = 20 // 2일을 마치고 7일에 얻은 최대 금액 20 저장

 

...

 

N일차 

dp[n] = 0 // 다음날 nxt = n + Tn 

dp[nxt] = Math.max( dp[nxt], dp[n] + Pn) 

 

풀면서 놓쳤던점

오랜만에 알고리즘 문제를 풀면서 처음에 다이나믹 접근법을 잊어먹었다. 그래서 처음에 푸는 시간이 굉장히 오래 걸렸다.

 

이 문제를 통해 얻어갈 것

다이나믹 프로그래밍(DP)

 

내 코드 

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

class Main {

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

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[][] arr = new int[n + 2][2];
        int[] dp = new int[n + 2];
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());

            int day = Integer.parseInt(st.nextToken());
            int pay = Integer.parseInt(st.nextToken());
            arr[i][0] = day; // 기간
            arr[i][1] = pay; // 금액
        }

        int max = -1;
        for (int i = 1; i <= n + 1; i++) {
            if (max < dp[i]) {
                max = dp[i];
            }

            int nxt = i + arr[i][0];
            if (nxt < n + 2) {
                dp[nxt] = Math.max(dp[nxt], max + arr[i][1]);
            }
        }
        System.out.println(dp[n + 1]);
    }
}