[BOJ] 15486. 퇴사 2

문제 원본 : https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n + 1][2];
        int[] dp = new int[n + 1];
        StringTokenizer st;

        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());

            dp[i] = Math.max(dp[i], dp[i - 1]);

            int tmp = i + arr[i][0] - 1;
            if (tmp <= n) {
                dp[tmp] = Math.max(dp[tmp], dp[i - 1] + arr[i][1]);
            }
        }

        bw.write(String.valueOf(dp[n]));

        bw.close();
        br.close();
    }
}

• 다이내믹 프로그래밍 문제
• Max(전 날까지 번 금액 + 오늘부터 상담해서 벌 수 있는 금액)을 구하면 해결된다.