백준 2749번: 피보나치 수 3

문제 설명

• n번째 피보나치 수를 구해야 합니다.

접근법

• 피보나치 수의 일반적인 공식은 F(N) = F(N-1) + F(N-2)입니다. 이렇게 계산할 경우 시간복잡도는 O(N)이 됩니다.

• 다른 규칙을 찾아봅시다.

  F(N) = 1 * F(N-1) + 1 * F(N-2)
  = [F(N-2) + F(N-3)] + F(N-2) = 2 * F(N-2) + F(N-3)
  = 2 * [F(N-3) + F(N-4)] + F(N-3) = 3 * F(N-3) + 2 * F(N-4)
  = 3 * [F(N-4) + F(N-5)] + 2 * F(N-4) = 5 * F(N-4) + 3 * F(N-5)
  = 8 * F(N-5) + 5 * F(N-6)
  = 13 * F(N-6) + 8 * F(N-7)

• 피보나치를 분해해보니 앞자리 숫자들이 다시 피보나치를 이루고 있습니다. 이를 공식화하면 다음과 같습니다.

  F(N) = F(K+1) * F(N-K) + F(K) * F(N-1-K)

• 이 규칙을 활용하는 가장 좋은 방법은 K를 N의 절반으로 설정해 이분탐색처럼 반씩 줄여나가는 겁니다. 이때 홀수인 경우와 짝수인 경우를 다음과 같이 구분할 수 있습니다.

  • N = 2a, K = a인 경우

    F(2a) = F(a+1) * F(2a - a) + F(a) * F(a-1) = F(a+1) * F(a) + F(a) * F(a-1)

  • N = 2a+1, K = a인 경우

    F(2a+1) = F(a+1) * F(2a+1-a) + F(a) * F(2a+1-1-a) = F(a+1) * F(a+1) + F(a) * F(a)

• 순차적으로 피보나치 값을 찾을 떄는 list형태에 이전값을 저장해두면 좋습니다. 하지만 이 경우 순차적으로 값을 찾지 않으므로 list가 아닌 map에 값을 저장해 뒀습니다.

정답

public class Main {

    public static int moduleNum = 1_000_000;
    public static Map<Long,Long> map = new HashMap<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long n = Long.parseLong(br.readLine());
        map.put(0L,0L);
        map.put(1L,1L);
        map.put(2L,1L);
        System.out.println(fibo(n));

    }

    public static long fibo(long n) {
        if(map.containsKey(n)) return map.get(n);
        if(n%2 == 0) {
            long a = n/2;
            long result = (fibo(a + 1) * fibo(a)) % moduleNum + (fibo(a) * fibo(a - 1)) % moduleNum;
            result%=moduleNum;
            map.put(n,result);
            return result;
        }else {
            long a = n/2;
            long result =(fibo(a+1) * fibo(a+1))%moduleNum + (fibo(a) * fibo(a))%moduleNum;
            result%=moduleNum;
            map.put(n,result);
            return result;
        }
    }

}