백준 14501 퇴사 (Java)

1. 문제 링크

14501번: 퇴사

 

2. 문제 및 입출력예제

 

3. 문제 풀이

dp 느낌으로 뒤에서부터 시작했다.

끝나는 날이 퇴사 이후라면 이전과 같은 금액이다.

그 외의 경우에는 상담 이전 금액과 지금 금액 + 이후 금액의 합 중 큰 값이 오면 된다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] split;
		int[] T = new int[N+1];
		int[] P = new int[N+1];
		int[] sum = new int[N+2];
		for(int i=1;i<N+1;i++) {  //1일부터 시작
			split = br.readLine().split(" ");
			T[i] = Integer.parseInt(split[0]); //끝나는 날은 i+T[i]
			P[i] = Integer.parseInt(split[1]);
		}
		
		for(int i=N;i>0;i--) {
			if(i+T[i] > N+1) { //기간이 퇴사 후 라면 이전 값 유지
				sum[i] = sum[i+1];
			}
			else {
				sum[i] = Math.max(sum[i+1], P[i]+sum[i+T[i]]); 
			}
		}
		System.out.println(sum[1]);
		
	}
}