[백준] 1788 피보나치 수의 확장 - 동적프로그래밍(DP, Dynamic Programming) + 수학(Math) JAVA

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

코드설명

동적프로그래밍(DP, Dynamic Programming) + 수학(Math) 을 활용합니다.

 

처음에 문제에서 개선시켰던 점은,

1. % MOD를 어느부분에 정확히 해야하나?

아래와 같이 하나의 MOD로 분배 법칙에 의해 자동으로 나눠집니다.

    return cache[n] = (plusFibo(n - 1) + plusFibo(n - 2) ) %MOD ;

 

2. minusFibo, plusfibo로 두개의 함수로 나누어서 처리했는데, 한개의 함수로 바꿔서 깔끔하게 구현도 가능할 것 같지만, 원활하게 2개루 구현했습니다. (무엇이 더 나은지는 모르겠습니다.) 단순히 if(n > 0) 혹은 (n < 0) 이렇게 처리하고 하면 되겠지요. 또, F[-1) == 1, 반드시 1이라는 것은 알 수 있으니 이를 기저조건으로 두면 되겠지요.

 

3. 저는 아래와 같이 직접 식을  F(n) = F(N+2) - F(N+1) 이라는 식을 세워서 구현했는데,

다른 분들이 본 코드를 보니, F(-1) 과 F(1), F(-2)와 F(2), ... 결국 피보나치 수가 같았습니다. 음수일때 짝수인경우(-2, -4, -6, ... 일때만 음수로 바꿔서 처리)만 부호가 다르므로 부호만 바꾸어서 반환하면 됩니다. 이렇게 규칙을 찾을경우 훨씬 빠르게 계산해낼 수 있습니다.

코드

처음에 푼 코드입니다.

package Main;

import java.util.*;
import java.io.*;

public class Main {
    public static int N, M;
    public static int[] cache;
    public static int answer = 0;
    public static int MAX = (int) Math.pow(10, 6);
    public static int MOD = (int) Math.pow(10, 9);
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		N = Integer.parseInt(st.nextToken());
		cache = new int[MAX + 1];
		Arrays.fill(cache, Integer.MIN_VALUE);
		if(N >= 0) {
			answer = plusFibo(N);
			if(answer > 0) System.out.println(1);
			else if(answer == 0) System.out.println(0);
			else System.out.println(-1);
			System.out.println(answer);
		}
		else if(N < 0) {
			answer = minusFibo(N);
			
			if(answer > 0) System.out.println(1);
			else if(answer == 0) System.out.println(0);
			else System.out.println(-1);
			
			System.out.println(Math.abs(minusFibo(N)));
		}
	}
   
    public static int plusFibo(int n) {
    	if(n == 0) return 0;
    	if(n == 1) return 1;
    	if(cache[n] != Integer.MIN_VALUE) return cache[n];
    	
    	return cache[n] = (plusFibo(n - 1) + plusFibo(n - 2) ) %MOD ;
    }
    
    public static int minusFibo(int n) {
    	if(n == 0) {
    		return 0; 
    	}
    	if(n == 1) {
    		return 1;
    	}
    	if(cache[n + MAX] != Integer.MIN_VALUE) return cache[n + MAX];
    	
    	return cache[n + MAX] = (minusFibo(n + 2) - minusFibo(n + 1) ) % MOD; 
    }
    
}