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

Ga0·2024년 9월 8일

Java baekjoon 백준 자바

baekjoon

목록 보기

135/137

문제 해석

N을 입력받아 N번째 피보나치 수를 구한 후 1,000,000,007로 나눈 나머지를 구하면 되는 문제이다.
Fn(N번째 피보나치)를 구하기 위해서 행렬제곱을 사용한 방식이다. (처음에는 그냥 피보나치 수를 재귀방식으로 더하는 방식으로만 생각했는데 다른 풀이를 보니 행렬제곱을 적용한 방식이었다,,,)
이 로직으로 코드를 작성하면 된다.

코드

내 마음대로 코드

import java.io.*;

public class Main {
    final static int 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()); //행렬 A의 NxN

        long result = 0;

        result = fibonachi(0, 1, N);

        System.out.println(result);
    }

    public static long fibonachi(long n1, long n2, long cnt) { //피보나치 구하는 메소드 
        if(cnt == 0L) {
            return n1%MOD;
        }
        if(cnt == 1L){
            return n2%MOD;
        }

        long result = fibonachi(n2%MOD, (n1+n2)%MOD, cnt-1);

        return result;
    }
}

그냥 답만 뽑아내기 위해 작성한 코드인데 당연히 틀린 코드 였고 (런타임 에러)... 좀 반성했다ㅠㅠ

이해 후 작성한 코드

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

public class Main {

    static long MOD = 1000000007; //니눠야하는 수
    static long[][] A = {{1, 1}, {1, 0}}; //A 행렬

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //구해야하는 피보나치 수 (N번째)
        long N = Long.parseLong(br.readLine());
        br.close();

        //피보나치 수를 구할 때
        /*  (예시, 7번째의 피보나치를 구한다 했을 때)
           Fn+1
           Fn
           이므로 n은 6만 들어가도 A(1,1)(정리상) = A(0,0)(자바 배열상) F7(7번째 피보나치 수)를 구할 수 있다.
           즉, N--은 감소시킨다.
         */

        N--;

        System.out.println(divide(A, N)[0][0]);

    }

    //행렬 제곱 분할정복
    static long[][] divide(long[][] matrix, long exp){

        //F0 = 0, F1 = 1이기 때문에 exp이 1과 0일 경우는 그대로 출력하면된다.
        if(exp == 1 || exp == 0){
            return matrix;
        }

        //지수 제곱하깆 전 절반으로 나눠 재귀
        long[][] result = divide(matrix, exp/2);

        //절반으로 나눈 값을 가져와 제곱한다.
        result = multiply(result, result);

        if(exp % 2 != 0L){ //홀수 제곱이라면
            result = multiply(result, A); //하나 초기값으로 한번더 곱한다.
        }

        return result; //제곱하면 제곱만큼 빠진다.
    }

    //행렬(파라미터)과 행렬(파라미터)을 곱해주는 메소드
    public static long[][] multiply(long[][] m1, long[][] m2){
        long[][] result = new long[2][2]; //피보나치 배열은 2x2형태의 행렬이다.

        //행렬 곱을 구하는 식이다.(곰셈하는 방식)
        result[0][0] = ((m1[0][0]*m2[0][0])+(m1[1][0]*m2[0][1]))%MOD; //A(1,1)
        result[0][1] = ((m1[0][0]*m2[0][1])+(m1[0][1]*m2[1][1]))%MOD; //A(1,2)
        result[1][0] = ((m1[1][0]*m2[0][0])+(m1[1][1]*m2[1][0]))%MOD; //A(2,1)
        result[1][1] = ((m1[1][0]*m2[0][1])+(m1[1][1]*m2[1][1]))%MOD; //A(2,2)

        return result;

    }
}