[백준 11444] 피보나치 수 6

문제 출처

사용 언어: Java

1. 구상

• 재귀를 이용하여 피보나치 계산 구현
• 계산한 피보나치 수 값을 배열에 저장 → 추후에 재사용
• 2차원 배열을 이용하여 피보나치 행렬 구현
  행렬 참고 링크
  
  

2. 구현

import java.util.*;
import java.io.*;

public  class Main {	
	final static long MOD = 1000000007;
	public static long[][] oddMat = {{1, 1}, {1, 0}};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long num = Long.parseLong(br.readLine());		
		
		long[][] mat = {{1, 1}, {1, 0}};
		
		System.out.println(fib(mat, num - 1)[0][0]);
		
	}
	
	
	public static long[][] fib(long[][] arr, long exp) {
		//지수가 1이하면 arr 그대로 return
		if(exp <= 1)
			return arr;
		
		//계산을 간단히 하기 위한 재귀호출
		long[][] re = fib(arr, exp/2);
		
		re = multi(re, re);
		
		if(exp % 2 == 1) {
			re = multi(re, oddMat);
		}
		
		
		return re;
	}
	
	
	public static long[][] multi(long[][] m1, long[][] m2) {
		//계산 결과를 저장할 행렬
		long[][] result = new long[2][2];
		
		result[0][0] = ((m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0])) % MOD;
		result[0][1] = ((m1[0][0] * m2[1][0] + m1[0][1] * m2[1][1])) % MOD;
		result[1][0] = ((m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0])) % MOD;
		result[1][1] = ((m1[1][0] * m2[1][0] + m1[1][1] * m2[1][1])) % MOD;
		
		return result;
	}
} 

코드 참고

- Scanner와 동일한 기능이나 속도가 더 빠른 BufferedReader로 입력 받기.

- 입력 받은 지수 / 2 값을 재귀호출한 후, 제곱하여 원하는 값 얻기.

- 홀수 지수일 경우, 추가로 기본 피보나치 행렬을 한 번 곱해준다.

- 행렬 곱셈 메소드(multi)에서 곱한 후, MOD값을 나눈 나머지를 행렬에 저장.