Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

8. 피보나치 수 6

11444번

행렬 곱셈을 응용해 피보나치 수를 구하는 문제

이번 문제는 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하는 문제입니다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이고, n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력하면 됩니다. 피보나치수를 행렬로 이용해서 푸는 방법입니다.

• Java

import java.util.Scanner;

public class Main {
	final static long MOD = 1000000007;
	public static void main(String[] ar){
		Scanner sc = new Scanner(System.in);
        long originN = sc.nextLong();
		long n = originN - 1;
		
		long[][] matrix = { {1, 1}, {1, 0} };
		long[][] resultMat = { {1, 0}, {0, 1} };

		while(n > 0){
			if(n%2 == 1) resultMat = Multi(resultMat, matrix);
			matrix = Multi(matrix, matrix);
			n/=2;
		}
		if(originN < 3){
			System.out.print(1);
		}else{
			System.out.print((resultMat[1][0]+resultMat[1][1]) % MOD);
		}
	}
	
	public static long[][] Multi(long[][] matrix1, long[][] matrix2){
		int m1 = matrix1.length;
		int n1 = matrix1[0].length;
		int m2 = matrix2.length;
		int n2 = matrix2[0].length;
		long[][] temp = new long[m1][n2];
		
		for(int i=0; i<m1; i++){
			for(int j=0; j<n2; j++){
				for(int k=0; k<n1; k++){
					temp[i][j] += matrix1[i][k]*matrix2[k][j];
				}
				temp[i][j] %= MOD;
			}
		}
		return temp;
	}
}

• Python

import sys
input = sys.stdin.readline
MOD = 1000000007
#초기 행렬
adj=[[1,1],[1,0]]
#피보나치 초기값
start=[[1],[1]]
N = int(input())

#제곱을 구하는 분할정복
def power(adj,n):
    if n == 1:
        return adj
    elif n % 2:
        return multi(power(adj,n-1), adj)
    else:
        return power(multi(adj,adj), n//2)
    
#행렬의 곱셈
def multi(a,b):
    temp=[[0]*len(b[0]) for _ in range(2)]
    for i in range(2):
        for j in range(len(b[0])):
            sum_n = 0
            for k in range(2):
                sum_n += a[i][k]*b[k][j]
            temp[i][j]= sum_n % MOD
    return temp

if N < 3:
    print(1)
else:
    print(multi(power(adj,N-2),start)[0][0])