백준 14501번 퇴사(JAVA)

[풀이방식]

처음엔 그리디로 해결할 수 있을거라 생각하여 특정 지점에서 최선의 선택을 하는 방식으로 풀었으나 계속 틀렸다.
1일에 상담을하면 4일부터 상담이 바로 가능하지만 4일에는 하지않고 5일부터 하는 것이 더 최선의 선택일 수도 있기때문에 그리디로 푸는 것이 잘못되었음을 알았고 매 지점에서 최선의 선택을 고르기 위해 DP로 풀었다.

뒤에서 앞으로 가면서 특정 지점에서 상담 날짜가 데드라인을 벗어난다면 패스하고 안넘기는 경우에는 당일에 상담을 하는지 안하는지 둘중의 최대값을 선택해 나갔다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<>();
		
		int deadline = sc.nextInt();

		int [] T = new int [deadline+1];
		int [] P = new int [deadline+1];
		int [] value = new int[deadline+2];

		for(int i = 1 ; i < deadline+1 ; i++) {
			T[i] = sc.nextInt();
			P[i] = sc.nextInt();
		}
		
		Arrays.fill(value, 0); // 일단 전부 0으로 초기화
		
		for(int i = deadline;  i >0; i--) {
			int nextday = i+T[i]; // 다음 상담하는 날짜
			
			//데드라인 안넘기면
			if(nextday <= deadline +1)
				//당일 일한다면 P[i] + value[nextday]
				//당일 일안한다면 그다음 최대값은 value[i+1]
				value[i] = Math.max(P[i] + value[nextday], value[i+1]);
			
			//데드라인 넘어가는건 패스
			else
				value[i] = value[i+1];
		}
		
		int max = 0;
		for(int i = 0 ; i < value.length; i++) {
			if(value[i] > max) {
				max = value[i];
			}
		}
		System.out.println(max);
	}	
}