[Java] 백준 11444번 피보나치 수 6 - 도가뉴 항등식

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

11444번: 피보나치 수 6

n번째 피보나치 수를 찾아야 하는데, n의 최대값이 1,000,000,000,000,000,000이다.

long 최대 범위 근접하는 엄청난 범위라서

도가뉴 항등식을 사용해야 한다.

단순히 재귀만 사용하면 시간복잡도를 많이 줄일 수가 없어서

TreeMap에 각 피보나치 수를 저장한다.

이미 저장된 값이 있다면 조회만 하면 끝!

 

시간복잡도 관리의 중요성을 상기시켜주는 문제였다.

참고로 m이 n보다 크거나 같아야 잘 동작하게 짜놓았다.

 

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

public class g2_11444{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static long k = 1000000007;
    static Map<Long, Long> map = new TreeMap<>();
    
    public static void main(String[] args){
        long n = fs.nextLong();
        map.put((long)0, (long)0);
        map.put((long)1, (long)1);
        map.put((long)2, (long)1);

        pw.println(docagne(n));
        pw.close();
    }

    static long docagne(long m_plus_n){
        if (map.containsKey(m_plus_n)){
            return map.get(m_plus_n);
        }

        long n = m_plus_n / 2;
        long m = m_plus_n - n;

        long temp = (((docagne(m - 1) * docagne(n)) % k) + ((docagne(m) * docagne(n + 1)) % k)) % k;
        map.put(m_plus_n, temp);
        return temp;
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}