BOJ 14501 퇴사

14501번: 퇴사

다이나믹 프로그래밍? 혹은 브루트포스 ? 문제이다.

일단 1일차부터 N일차까지 각 상담을 첫 상담으로 한다고 하면,

i일차 상담 + ( [i일차 상담이 끝나는 날짜~N일차 상담] 중에서 가장 이득이 큰 상담)이 해당 일차의 가장 이득이 높은 상담이 될 것이다. 그러면 또 i일차 상담이 끝나는 날짜 ~ N일차 상담 중에서 가장 이득이 큰 상담을 구하려면,

해당 일자를 j 일로 놓고 j일차 상담 + ( [ j일차 상담이 끝나는 날짜~ N일차 상담 ] 중에서 가장 이득이 큰 상담) 을 구하면 된다.

그러면 이걸 1일차부터 N일차까지 모두 구하면 되는 것이다.

이걸 더 완벽한 DP로 풀기위해서는 bottom - up으로 각 일자마다 [ i일차 상담이 끝나는 날짜~ N일차 상담 ] 중에서 가장 이득이 큰 상담 을 테이블에 저장하면 되지 않을까 싶다 

import java.util.*;
import java.io.*;
// 2차원 배열 0 에는 상담 걸리는 일수
// 2차원 배열 1 에는 상담 이득 저장 
public class Main {
	static int[][]input;
	public static void main(String[]args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		input = new int[n][2];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			input[i][0] = Integer.parseInt(st.nextToken());
			input[i][1] = Integer.parseInt(st.nextToken());
		}
		int max = 0;
		int get = 0; 
		
		for(int i=0; i<n ; i++) { // 1일차~부터 N일차까지 시작점으로 지정 
			if(input[i][0]+i>n) continue; //퇴사 이후가 상담이 끝나는 날이면 넘어가기
			get = solve(i,n); // i일차에 시작하는 상담 중 가장 이득이 큰 상담 고르기 
			if(get > max) max =get; // 현재까지 max와 비교 
		}
		System.out.println(max);
		
	}
	
	static int solve(int idx, int n){
		int max = 0;
		int sum = 0;
		for(int i = idx; i < n ; i++) {
			if(input[i][0]+i>n) continue; //퇴사 일자 넘는것 건너뛰기
			sum+=input[i][1]+solve(input[i][0]+i,n);
			if(sum > max) max = sum;
			sum = 0;
		}
		return max;
	}
}