이번에 풀어본 문제는
백준 15486번 퇴사 2 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        int [] dp = new int[N+1];
        int max_val = Integer.MIN_VALUE;
        for(int i = 0; i <= N; ++i)
        {
            max_val = Math.max(max_val,dp[i]);

            int next = i + t[i];
            if(next <= N)
            {
                dp[next] = Math.max(dp[next],max_val+p[i]);
            }
        }
        System.out.print(max_val);
    }
}

📝 풀이

퇴사일까지 최대로 얻을 수 있는 수익을 출력하는 문제입니다.
dp배열은 해당 근무일까지 낼 수 있는 수익의 최댓값을 지니고 있습니다.
당일 업무를 건너뛰는 경우가 더 큰 수익을 낼 수도 있기 때문에, 반복의 시작부분에서 max값보다 작다면 현재 인덱스의 dp값을 고려하지 않고 넘어갈 수 있도록 합니다. 매 반복마다 갱신되는 max값을 출력하면 해결됩니다.

📜 후기

이번에도 dp 문제입니다. 매번 새롭네요... 많이 풀다보면 적응 될 것이라 믿습니다!ㅋㅋ