[백준] 9711 피보나치 - 동적계획법(DP, Dynamic Programming) + 재귀(Recursive) JAVA

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

코드설명

동적계획법(DP, Dynamic Programming) + 재귀(Recursive) 를 활용합니다.

 

문제에서 유의해야할점은,

1.  %Q를 매번 처리하여서 OverFlow가 나지않도록 해야 합니다.

return cache[n] = ( fibo(n - 1) + fibo(n - 2) )%Q;

추가로, 함수 호출부분에도 추가해주어야 마지막에 더해준값도 올바르게 오버플로우가 나지 않게 처리합니다.

sb.append("Case #").append(idx).append(": ").append(fibo(P) % Q).append("\n");

 

2. Cache 배열은 새로운 P와 Q, 테스트케이스마다 초기화해야합니다.

while(idx++ < T) {
    Arrays.fill(cache, -1);
    st = new StringTokenizer(br.readLine());	
    int P = Integer.parseInt(st.nextToken());
    Q = Integer.parseInt(st.nextToken());

    sb.append("Case #").append(idx).append(": ").append(fibo(P) % Q).append("\n");
}

피보나치수는 항상 정해진것이기에 밖에서 한번만 초기화하고, 매번 함께 사용하려고 하였으나, 매번 %Q, 즉 다른 Q값으로 초기화되기에 항상 새로 -1 로 초기화한뒤 시작해야 합니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static int Q;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        T = Integer.parseInt(st.nextToken());
        cache = new long[10001];
        int idx=0;
        while(idx++ < T) {
        	Arrays.fill(cache, -1);
        	st = new StringTokenizer(br.readLine());	
        	int P = Integer.parseInt(st.nextToken());
        	Q = Integer.parseInt(st.nextToken());
        	
        	sb.append("Case #").append(idx).append(": ").append(fibo(P) % Q).append("\n");
        }
        System.out.println(sb);
    }
    
    private static long fibo(int n) {
    	if(n == 1 || n == 2) return 1;
    	if(cache[n] != -1) return cache[n];
    	
    	return cache[n] = ( fibo(n - 1) + fibo(n - 2) )%Q;
//    	return cache[n] = ( fibo(n - 1) % Q + fibo(n - 2) % Q) % Q;
    }
    
    
}