[BaekJoon] 11444번 피보나치 수 6 (Java) 문제 풀이 [Gold 2]

문제

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

11444번: 피보나치 수 6

 

어떻게 풀 것인가?

처음에 보고 조금 당황스러웠다.

DP로 풀기에는 너무나도 큰 수 이다. 아마 처음에 단순 DP로 접근했다면 분명히 시간초과가 발생했을 것이다.

그렇다면 이러한 시간초과 부분을 획기적으로 줄일 수 있는 것이 무엇이 있을까?

 

바로 행렬이다.

 

사실 백준알고리즘을 많이 풀어본 이들이라면 위와 같은 피보나치 문제들은 많이 봐왔기 때문에 아래와 같은 점화식은 익숙할 것이다.

 

D(n+2) = D(n+1) + D(n) ( D0 = 0, D1 = 1, n >= 0)

 

이제 이러한 수식을 행렬로 만들어서 풀면된다.

 

자세한 내용은 아래 블로그를 참고하자.

https://st-lab.tistory.com/252

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]

 

즉 위와 같은 알고리즘을 "분할정복을 이용한 거듭제곱" 이라고 부르며 

https://nahwasa.com/entry/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1-%EC%B5%9C%EC%A0%81%ED%99%94

분할 정복을 이용한 거듭제곱 최적화

위의 블로그를 참고하면 풀이가 쉬울 것이다.

 

즉, O(logN) 시간복잡도를 갖기 때문에 1,000,000,000,000,000,000 번째 피보나치도 60번의 연산만 하면 끝나게 된다.

 

풀면서 놓쳤던점

분할정복을 이용한 거듭제곱에 대해서 잘 몰랐다. 기회가 되면 블로그에 추후 정리를 해야겠다.

 

이 문제를 통해 얻어갈 것

분할정복을 이용한 거듭제곱, 행렬의 사용

 

내 코드 

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

// 백준알고리즘 11444번 피보나치 수 6
public class Main {

    private static final long MOD = 1000000007;
    static Long N;

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

    private static long[][] matrixMult(long[][] a, long[][] b) {
        long[][] arr = new long[2][2];
        arr[0][0] = ((a[0][0] * b[0][0]) + (a[0][1] * b[1][0])) % MOD;
        arr[1][0] = ((a[0][0] * b[0][1]) + (a[0][1] * b[1][1])) % MOD;
        arr[0][1] = ((a[1][0] * b[0][0]) + (a[1][1] * b[1][0])) % MOD;
        arr[1][1] = ((a[1][0] * b[0][1]) + (a[1][1] * b[1][1])) % MOD;
        return arr;
    }

    private static long[][] fibo(long n) {
        if (n == 1 || n == 0) {
            return new long[][]{{1, 1}, {1, 0}};
        }

        long[][] tmp = fibo(n / 2);

        if (n % 2 == 1L) {
            return matrixMult(matrixMult(tmp, tmp), new long[][]{{1, 1}, {1, 0}});
        } else {
            return matrixMult(tmp, tmp);
        }
    }
}

 

참고

https://st-lab.tistory.com/252

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]