[백준] 15486번 퇴사 2 java

dp는 너무 어렵다. 쉬운 난이도이지만 한참 생각하고 헤맸다..
dp에서 중요한 것은 가장 먼저 dp[i]가 무엇인지 정의하고 점화식을 찾는 것이다.

문제 풀이 과정

1. dp[i] = i번째 날까지 최대 수익이라고 하자.
2. 우선 i+t[i]-1이 n을 초과하면 그 상담은 진행할 수 없다.

• N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

3. 만약 i번째 날의 상담을 선택한다면

• i+t[i]-1 날에 상담이 끝나고 돈을 받을 수 있다.
• 즉 p[i] + dp[i-1] (현재 날짜 이전까지의 최대 수익+현재 수익)이 i번째 날짜의 상담을 선택했을 때 최대 수익이 된다.
• 기존의 dp[i+t[i]-1]의 수익과 p[i] + dp[i-1]를 비교하여 큰 값을 dp[i+t[i]-1]에 저장한다.

4. 여기서 중요한 것은 dp[i]의 값은 매번 이전 날까지의 최대 이익으로 갱신해야한다. dp[i]=Math.max(dp[i-1],dp[i])

• 이 부분이 이해가 잘 안갔는데, 이렇게 갱신을 해주지 않으면 i번째 날의 상담을 선택하지 않았을 때 그냥 넘어가게 되면 이전 날짜까지의 최대 수익이 반영되지 않고 날아가버린다.

사실 p[i] + dp[i-1] 부분이 이해가 잘 되지 않았다. i번째 날짜의 상담을 선택했을 때 i번째 날의 수익을 더하는 것은 이해가 되지만, dp[i-1]을 더하는 것이 문제가 없을까라는 의문이 있었다.

만약 dp[i-1]에서 이전 날짜 중 i번째 상담을 선택하지 못하는 경우의 수가 포함되어 최대 수익이 산정됐다면 dp[i-1]을 더하는 것이 문제이지 않을까 싶었다.
근데 다시 생각해보니 dp[i-1] = i-1번째 날까지의 최대 수익이라는 것을 잊었다.
예를 들어 3일차 최대 수익을 고려할 때 dp[3-1]=dp[2]가 된다. 2일차를 선택한다면 상담이 5일이나 걸려서 3일차 상담을 못하겠지만 이는 dp[2]에는 반영되지 않는다. 어차피 상담 끝나는 기간인 2+5-1=6일차 dp값에 수익이 반영되기 때문이다.

dp에서 중요한 것은 처음 dp값을 무엇으로 정의했느냐와 점화식인걸 느꼈다.
dp 배열을 이용하여 이전까지의 최적의 값을 누적하여 활용해야함을 기억해야한다.

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

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 t[] = new int[n+2];
        int p[] = new int[n+2];
        int dp[] = new int[n+2];

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            t[i]=Integer.parseInt(st.nextToken());
            p[i]=Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++){
            dp[i]=Math.max(dp[i-1],dp[i]);
            if(i+t[i]-1<=n)
                dp[i+t[i]-1]=Math.max(dp[i+t[i]-1],dp[i-1]+p[i]);
        }
        System.out.println(Arrays.stream(dp).max().getAsInt());

        
    }
}