[BaekJoon] 11444 피보나치 수 6 (Java)

1.  문제 링크

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

2.  문제

요약

• 피보나치 수는 0과 1로 시작하고, 0번째 피보나치 수는 0, 1번째 피보나치 수는 1입니다.
• 그 다음 2번째부터는 바로 앞 두 피보나치 수의 합이 됩니다.
• 이를 식으로 써보면 $F_n = F_{n - 1} + F_{n - 2}$ (n ≥ 2) 가 됩니다.
• n이 주어졌을 때, n번째 피보나치 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1,000,000,000,000,000,000보다 작거나 같은 자연수인 n이 주어집니다.
• 출력: 첫 번째 줄에 n번째 피보나치 수를 1,000,000,007로 나눈 나머지를 출력합니다.

3.  소스코드

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

public class Main {
    static final int DIVIDE = 1000000007;
    static long n;

    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextLong();
    }

    static void solution() {
        System.out.println(findFibo(n - 1));
    }

    static int findFibo(long size) {
        int[][] mat = new int[][] {{1, 1}, {1, 0}};
        int[][] result = powMat(mat, size);

        return result[0][0];
    }

    static int[][] powMat(int[][] mat, long power) {
        if(power == 1 || power == 0) return mat;

        int[][] temp = powMat(mat, power / 2);

        if(power % 2 == 0)
            return mulMat(temp, temp);
        else
            return mulMat(mulMat(temp, temp), mat);
    }

    static int[][] mulMat(int[][] mat1, int[][] mat2) {
        int size = 2;
        int[][] result = new int[size][size];

        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) {
                long temp = 0;

                for(int idx = 0; idx < size; idx++) {
                    temp += ((long)mat1[row][idx] * mat2[idx][col]) % DIVIDE;
                }

                result[row][col] = (int)(temp % DIVIDE);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

4.  접근

• https://foggy-manuscript-f72.notion.site/11444-03dc4b77d66245a489ac34a1a6684d1a
• 위 링크를 통해 해당 문제의 접근 방법을 설명하였습니다.