백준 14501 퇴사

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Retirement {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] T = new int[N+1];
        int[] P = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }
        long[] dp = new long[N+2];
        for (int i = N; i >= 1; i--) {
            int next = T[i] + i;
            if(next<=N+1){
                dp[i] = Math.max(dp[i+1],dp[next] + P[i]);
            }
            else{
                dp[i] = dp[i+1];
            }
        }
        System.out.println(dp[1]);

    }
}

풀이방법

우선 dp배열에 어떤 점화식으로 통해 P값을 넣어야 할지 알아보기 위해 가능한 경우의 수를 하나씩 나열해본다.
1 4 5
2
3 4 5
4 5
5
0
0
👉 나중에 상담한 값이 이전의 dp값에 영향을 미치는 것을 확인할 수 있다. 즉, dp[i] = dp[i+1] + k; 이런식의 점화식 구조를 가진다.
따라서, dp에 뒤쪽 인덱스부터 채워 넣기 시작해야 한다.

이때, 나중에 상담한 값중 일부를 포기하고, 현재 P[i]를 선택했을때 더 높은 값이 나오는 경우의 수가 있다.
따라서 1. dp[i] = 나중에 상담한 값중 일부 포기한 값 + 현재 P[i]
2. 현재 날짜에 상담 안함. 즉, dp[i] = dp[i+1]
두개 중에 큰 값을 고른다.

📢이 조건은 T[i] + 현재 날짜(i)가 N+1 일때만 적용하며, 이 범위를 벗어나면 그냥 dp[i] = dp[i+1]를 넣어준다.

이후 dp[1]에는 담길 수 있는 P[i]의 최대의 값이 들어가므로, dp[1]을 출력해 준다.

후기

인덱스의 끝에서부터 탐색하며, 그중 두개의 조건중 최댓값을 dp에 담는 문제였다.
나에겐 어려운 문제였다.