[Java] 백준 15486번 퇴사 2

다이나믹 프로그래밍 문제입니다.
상담을 적절히 해서 최대 수익을 구해야 합니다.

매일 상담은 한 건이 있으며 해당 상담에 대하여 시간과 값이 주어집니다.
뒤에서부터 탐색하여 해당 상담이 가능한지 확인합니다.
그리고 다음의 점화식을 사용합니다.

dp[i] = Math.max(value[i] + dp[i + time[i] + 1], dp[i + 1]);

아래 두개를 비교해서 큰 값을 현재 날짜의 최대 값으로 저장합니다.

1. 현재 위치의 값 + 현재 상담을 마무리 했을 때 다음 상담으로 얻을 수 있는 최대값
2. 내일 얻을 수 있는 최대 값 (오늘 상담을 하지 않는 경우)

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

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

		int ans = 0;
		int n = Integer.parseInt(br.readLine());
		int[] time = new int[n];
		int[] value = new int[n];
		int[] dp = new int[n + 1];

		for (int i = 0; i < n; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken());

			time[i] = a;
			value[i] = b;
		}

		for (int i = n - 1; i >= 0; --i) {
			if (i + time[i] >= n) {
				dp[i] = dp[i + 1];
				continue;
			}
			dp[i] = Math.max(value[i] + dp[i + time[i] + 1], dp[i + 1]);
		}
		ans = dp[0];

		bw.write(ans + "\n");
		bw.close();
	}
}