[BOJ] 11444 : 피보나치 수 6 (Java)

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

11444번: 피보나치 수 6

걸린 시간 : 36분 32초

---

재밌을 것 같아서 도전! 했는데,,

숫자가 너무 크다. 이러면 무조건 O(logN) 알고리즘을 써야 하고, 그렇단 말은 F(2n) 과 F(n) 과의 관계를 알아내면 끝이다.

...

...

도대체 무슨 관계가 있는지 전혀 감도 안 오고 배운 적도 없는 것 같다..

이런 너무 수학적인 주제를 공부할 시간에 코딩 공부를 좀 더 하자는 핑계 생각에 잠깐 검색을 해보았더니 이런 식이 나온다.

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

이걸 제가 어떻게 알아요

이 식의 m에 n, n+1 을 대입해 정리하면 이렇게 나온다.

• F(2n) = F(n) ( 2F(n-1) + F(n) )
• F(2n+1) = (F(n))^2 + (F(n+1))^2

이 수식과 함께 다이나믹 프로그래밍으로 저장해서 재호출을 막도록 하자.

또한, 그냥 배열에 넣으면 당연히 저장공간이 터지기 때문에 HashMap 을 사용하자.

정답 코드

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class BOJ11444 {
 
    static Map<Long, Long> map = new HashMap<>();
    static long n;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        System.out.println(fib(n));
    }
 
    static long fib(long k) {
        if (map.containsKey(k)) {
            return map.get(k);
        }
        if (k == 0) return 0;
        if (k == 1) return 1;
        if (k % 2 == 1) {
            long ans = (fib(k/2) * fib(k/2)
                    + fib(k/2+1) * fib(k/2+1)) % 1000000007;
            memo(k, ans);
            return ans;
        }
        long ans = (fib(k/2) * (2*(fib(k/2-1)) + fib(k/2))) % 1000000007;
        memo(k, ans);
        return ans;
    }
 
    static void memo(long k, long ans) {
        if (map.containsKey(ans)) return;
        map.put(k, ans);
    }
}