[백준] 11444 : 피보나치 수 5 JAVA 풀이

import java.io.*;
import java.util.*;
public class Main {
	final static long MOD = 1000000007;
	static long[][] fibo = {{1,1},{1,0}};
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        // n을 입력받음
		long N = Long.parseLong(br.readLine());
		
        /*
        		행렬의 곱을 이용해 피보나치 수를 구하면
                Fn+1   Fn
                Fn     Fn-1
                의 값을 가지는 행렬을 구할 수 있음
                
                따라서 피보나치 기본값 행렬을 N-1번 제곱하고
                그 행렬의 [0][0]에 저장된 값을 출력하면 됨
        */
		System.out.println(findFibo(N-1)[0][0]);
	}
	
	static long[][] findFibo(long n) {
		
        // n이 1이면 기본 행렬을 반환함
		if(n<2) {
			return fibo;
		}
		
        // n을 분할해서 재귀호출함
		long[][] tmp = findFibo(n/2);
		
        // n/2 제곱을 구한 것끼리 곱해서 n제곱의 값을 구함
		tmp = multiply(tmp, tmp);
		
        // n이 홀수라면 기본값 행렬을 한 번 더 곱해줌
		if(n%2==1) {
			tmp = multiply(tmp, fibo);
		}
		// 계산한 행렬을 반환함
		return tmp;
	}
    
    // [2x2] 행렬 두 개를 곱하는 함수
	static long[][] multiply(long[][] a, long[][] b){
		long[][] tmp = new long[2][2];
		for(int i=0;i<2;i++) {
			for(int j=0;j<2;j++) {
				for(int k=0;k<2;k++) {
					tmp[i][j] += a[i][k]*b[k][j];
					tmp[i][j] %= MOD;
				}
			}
		}
		return tmp;
	}
}