[백준 2749] 피보나치 수 3

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

2749번: 피보나치 수 3

 

 

행렬 곱셈

 

이랑 푸는 방식이 동일함.

 

 

 

Fn+2 = Fn+1 + Fn

이라는 식을 행렬로 다음과 같이 바꿀 수 있음

 

 

위의 식을 이용하여 피보나치 수의 값을 구하는 연산의 시간복잡도를 logN으로 줄일 수 있음.

 

 

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

public class Main{
    public static void main(String [] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n = Long.valueOf(br.readLine());

        long arr[][] = {{0, 0, 0}, {0, 1, 1}, {0, 1, 0}};

        arr = power(arr, n);

        System.out.println(arr[2][1]);

    }

    private static long[][] power(long arr[][], long B) {
        if(B==1)    return arr;
        if(B%2==1) return multiple(power(arr, B - 1), arr);
        long[][] res = power(arr, B / 2);
        return multiple(res, res);
    }

    //정사각형
    private static long[][] multiple(long arr1[][], long arr2[][]) {
        int len = arr1[1].length;
        long res[][] = new long[len][len];
        for (int a = 1; a < len; a++) {
            for (int b = 1; b < len; b++) {
                for (int i = 1; i < len; i++) {
                    res[a][b] = (res[a][b] + arr1[a][i] * arr2[i][b] % 1000000) % 1000000;
                }
            }
        }
        return res;
    }
}

 

 

++피보나치 수의 피사노 주기 라는 특징을 이용하여 더 쉽게 풀이할 수 있음..

(근데그걸어떻게떠올림 ㅡㅡ)