[백준] 14501 퇴사 - 동적계획법(Dynamic Programming, DP) JAVA

https://www.acmicpc.net/problem/14501

코드설명

동적계획법(Dynamic Programming, DP) 문제입니다.

 

처음에는, for문을 활용해서 가능한 날짜 조합을 모두 만드는 방식으로 진행하려 했습니다. 해당 방식도 물론 가능합니다.

 

for문과 재귀함수의 사용방법과 원리는 똑같으므로, 좀 더 친밀한 재귀함수를 사용했습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int N, K, M, L;
    private static int[] arr;
    private static int answer = 0;
    private static int[] T, P;
    private static int[] cache = new int[16];
    private static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		Arrays.fill(cache, -1);
		N = Integer.parseInt(st.nextToken());
		
		T = new int[N+1];
		P = new int[N+1];
		
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			T[i] = Integer.parseInt(st.nextToken());
			P[i] = Integer.parseInt(st.nextToken());
		}
		answer = func(1);
		System.out.println(answer);
    }
    
    private static int func(int t) {
    	if(t > N) return 0;
    	
    	if(cache[t] != -1) return cache[t];
    	
    	int ret = 0;
    	//안사고 넘어가는 경우.
    	ret = func(t + 1) + 0;
    	
    	if(t + T[t] <= N+1)
    		ret = Math.max(ret, func(t + T[t]) + P[t]);
    	return cache[t] = ret;
    }
    
//    private static int func(int t) {
//    	if(t >= N) return 0;
//    		
//    	int ret = 0;
//    	if(t == -1) {
//    		for(int i=1; i<=N; i++) {
//    			ret = Math.max(ret, func(i) + 0);
//    		}
//    	}
//    	
//    }
}