[JAVA] 백준 11444 - 피보나치 수 6

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

N번째 피보나치수를 10억 7로 나눈 나머지를 출력하는 문제이다.

N의 범위를 보면 알듯 일반적으로 사용하는 동적계획법이나 재귀를 이용해 풀면 반드시 시간초과가 난다.

F(n+1) = F(n)+F(n-1)라는 점화식을 

이런 식으로 나타낼 수 있으므로  (1 1 1 0) 행렬의 거듭제곱으로 N번째 피보나치수를 구할 수 있다고 한다.

이런 걸 어떻게 알아내는거지..

여튼 이걸 알았으니 일반적인 빠른 제곱 알고리즘을 이용해 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long mod = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long num = Long.parseLong(br.readLine());
        System.out.println(getFibbo(num-2));
    }

    public static long getFibbo(long target) {
        long[][] result = {{1, 1}, {1, 0}};
        long[][] unit = {{1, 1}, {1, 0}};
        while(target>0){
            if((target&1)==1){
                result = getMatrixMult(result,unit);
            }
            unit = getMatrixMult(unit,unit);
            target>>=1;
        }
        return result[0][0];
    }

    public static long[][] getMatrixMult(long[][] a, long[][] b){
        return new long[][]{{(a[0][0]*b[0][0]%mod + a[0][1]*b[1][0]%mod)%mod, (a[0][0]*b[0][1]%mod+ a[0][1]*b[1][1]%mod)%mod}
                ,{(a[1][0]*b[0][0]%mod+a[1][1]*b[0][1]%mod)%mod,(a[1][0]*a[0][1]%mod+a[1][1]*b[1][1]%mod)%mod}};
    }
}