[BaekJoon] 7677 Fibonacci (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int DIVISOR = 1_0000;
    static final int[][] FIBONACCI_MATRIX = new int[][]{{1, 1}, {1, 0}};

    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int digit;

    /*
     * 입력이 -1이라면 프로그램을 종료해야하므로 -1인지 판단하여 true/false 값을 반환한다
     */
    static boolean input() {
        digit = scanner.nextInt();
        return digit == -1;
    }

    /*
     * 주어지는 입력, 즉 구해야할 피보나치 수의 최대가 1,000,000,000번째 피보나치 수이기 때문에 단순히 피보나치 수열을 구한다면 시간 초과가 일어난다
     * 그러므로 문제에 주어진 피보나치 수열의 다른 수식인 행렬을 거듭제곱해나가며 입력으로 주어진 피보나치 수를 구한다
     * 이때, 우리가 구해야 할 것은 끝 4자리이고, 곱셈에 대해서는 modulo 연산의 분배법칙이 가능하므로 각 제곱하는 과정에서 끝 4자리만 남기는 modulo 연산을 진행한다
     */
    static void solution() {
        if (digit <= 1) {
            answer.append(digit).append('\n');
            return;
        }

        int[][] result = findFibonacci(FIBONACCI_MATRIX, digit);
        answer.append(result[0][1]).append('\n');
    }

    static int[][] findFibonacci(int[][] matrix, int exponent) {
        if (exponent == 1) {
            return matrix;
        }

        int[][] temp = findFibonacci(matrix, exponent / 2);
        int[][] result = multiplyMatrix(temp, temp);
        if (exponent % 2 != 0) {
            result = multiplyMatrix(result, matrix);
        }
        return result;
    }

    static int[][] multiplyMatrix(int[][] matrix1, int[][] matrix2) {
        int[][] result = new int[FIBONACCI_MATRIX.length][FIBONACCI_MATRIX[0].length];

        for (int row = 0; row < FIBONACCI_MATRIX.length; row++) {
            for (int col = 0; col < FIBONACCI_MATRIX[row].length; col++) {
                for (int idx = 0; idx < FIBONACCI_MATRIX[row].length; idx++) {
                    result[row][col] += matrix1[row][idx] * matrix2[idx][col];
                    result[row][col] %= DIVISOR;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        while (true) {
            if (input()) {
                break;
            }
            solution();
        }

        System.out.print(answer);
    }

    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();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}