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

문제 바로가기 : https://www.acmicpc.net/problem/11444

메모리 : 14292KB

시간 : 128ms

언어 : Java 11

---

코드

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

public class Main {
    static long mod = 1000000007;
    static long[][] origin = { { 1, 1 }, { 1, 0 } };

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

    public static long[][] pow(long[][] A, long e) {
        if (e == 1 || e == 0) {
            return A;
        }
        long[][] half = pow(A, e / 2);
        half = mult(half, half);
        if (e % 2 == 1) {
            half = mult(half, origin);
        }
        return half;
    }

    private static long[][] mult(long[][] o1, long[][] o2) {
        long[][] half = new long[2][2];
        half[0][0] = ((o1[0][0] * o2[0][0]) + (o1[0][1] * o2[1][0])) % mod;
        half[0][1] = ((o1[0][0] * o2[0][1]) + (o1[0][1] * o2[1][1])) % mod;
        half[1][0] = ((o1[1][0] * o2[0][0]) + (o1[1][1] * o2[1][0])) % mod;
        half[1][1] = ((o1[1][0] * o2[0][1]) + (o1[1][1] * o2[1][1])) % mod;
        return half;
    }
}

풀이

"분할 정복을 이용한 거듭 제곱" 이라는 것이 생소했다.. 찾아보니까 행렬을 이용해 시간복잡도를 줄이는 알고리즘이었다.
22222*2 이렇게 곱해야 하는 것을 ((2^2)^2)^2 거듭제곱을 이용하면 이와 같이 연산이 줄어든다.
이 거듭제곱을 이용한 시간줄이기가 홀수번제곱, 짝수번제곱일 때 풀이가 조금 다르다.

A^4 = (A^2)^2 (짝수일때)
A^5 = A * A^4 = A * (A^2)^2 (홀수일때)

이를 분할정복을 이용해 홀수일때, 짝수일때 나누어 계산할 수 있다.

private static long pow(long a, long n) {
    if (n == 1)
        return a;
    long tmp = pow(a, n/2);
    if (n%2==0)
        return tmp*tmp;
    else
        return a*tmp*tmp;
}

잘 이해는 안 됐지만 몇 번 더 풀어보면 익숙해질 것 같다!