[Java] 백준 14501번 퇴사

다이나믹 프로그래밍 문제입니다.

각 날짜마다 할 수 있는 상담이 주어졌을때 최대한의  이익을 계산하는 문제입니다.
점화식을 세울 수 있습니다.

DP[i+day[i]] = Math.max(DP[i+day[i]], DP[i] + pay[i]);

DP[현재 날의 상담 기간을 계산했을 때 끝나는 날]
= max(DP[현재 날의 상담 기간을 계산했을 때 끝나는 날], DP[현재 날까지 계산된 값] + pay[현재 날 상담을 통해 얻는 값])

DP[i+1] = Math.max(DP[i+1], DP[i]);

다음날의 계산된 결과 값, 오늘날의 계산된 결과 값 중 큰 값을 다음날 값에 삽입

위의 식들을 통해 최종적으로 가장 많이 얻을 수 있는 금액을 찾아낼 수 있습니다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] day = new int[n+1];
		int[] pay = new int[n+1];
		int[] DP = new int[n+1];
		for(int i=0; i<n; ++i) {
			day[i] = sc.nextInt();
			pay[i] = sc.nextInt();
		}
		
		for(int i=0; i<n; ++i) {
			if(i+day[i] <= n) {
				DP[i+day[i]] = Math.max(DP[i+day[i]], DP[i] +pay[i]);							
			}
			DP[i+1] = Math.max(DP[i+1], DP[i]);
		}
		
		System.out.println(DP[n]);
	}

}