풀이 아이디어

다이나믹 프로그래밍(DP)를 사용해서
(i-1)번째 날까지 얻을 수 있는 최대 이익을 Math.max()로 구하고 배열 dp[i]에 저장한다.
마지막 날에 일한 날과 아닌 날을 구분해서 n일과 n+1일 중 최대값을 구분해준다.

트러블 슈팅

1. 인덱스 문제

마지막 날까지 꽉 채워서 일하는 경우 최대 이익을 저장하는 dp[i] 배열에
인덱스가 1~n일을 넘어서 n+1일에 최대값을 구할 수 있도록 코드를 작성했다.
왜냐하면 마지막 날에 일해서 얻은 이익도 반영해야 되기 때문이다.
이 경우 dp[n+1] 값을 갱신해줘야 하는데 갱신 조건을 실수로 n일까지 할 수 있도록 작성해서
오류가 발생했다. 마지막 날에 일한게 반영이 안 되었기 때문이다.
그래서 n+1까지 갱신할 수 있도록 if문 조건을 변경했다.

before

if(i+schedule[i][0] < n+1)

after

if(i+schedule[i][0] < n+2)

2. 마지막날 일하는 경우와 아닌 경우 구분하기

원래는 마지막날까지 일한 걸 반영하는 dp[n+1]을 출력하도록 작성했다.
하지만 dp[n]과 dp[n+1]중에서 dp[n]이 더 커서 오류가 발생했다.
왜냐하면 스케줄을 어떻게 짜느냐에 따라서 마지막 전날까지 일한 dp[n]이 더 클 수 있었기 때문이다.
또한 코드에서 스케줄링을 i=n일때까지만 dp[i]와 dp[i-1]를 비교해서 갱신하기 때문이다.
그래서 n+1이 갱신되지 않았다.

for(int i=1;i<n+1;i++){
	dp[i] = Math.max(dp[i], i==1 ? 0 : dp[i-1]);
    ...
        }

어 그러면 n+1까지 dp[i], dp[i-1] 비교해서 갱신하면 되지 않느냐? 하는 의문이 들 수 있다. 하지만 그렇게하면 인덱스 오류가 발생했다.

그래서 마지막 전날까지 일한 dp[n]와 마지막 날까지 일한 dp[n+1] 중에서 더 큰 값을 출력하도록 변경했다.

before

System.out.println(dp[n+1]);

after

System.out.println(Math.max(dp[n+1], dp[n]));

풀이 코드

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

public class _15486 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] schedule = new int[n+1][2];
        // dp[i] = i번째 날까지의 최대 수익
        int[] dp = new int[n+2];
        for(int i=1;i<n+1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            schedule[i][0] = Integer.parseInt(st.nextToken());
            schedule[i][1] = Integer.parseInt(st.nextToken());
        }
        // 스케줄링 
        for(int i=1;i<n+1;i++){
            dp[i] = Math.max(dp[i], i==1 ? 0 : dp[i-1]);
            if(i+schedule[i][0] < n+2){
                dp[i+schedule[i][0]] = Math.max(dp[i+schedule[i][0]], dp[i]+schedule[i][1]);
            }
        }
        System.out.println(Math.max(dp[n+1], dp[n]));
    }
}