[BAEKJOON] 11444 피보나치 수 6

문제 요약

• 알고리즘 분류: 수학, 분할정복, 재귀 호출
• 난이도: Gold2
• 문제내용:
  • 피나치수 결과를 1,000,000,007로 나눈 나머지를 구해라

• 사이트 : https://www.acmicpc.net/problem/11444

11401번: 이항 계수 3

문제풀이

 이번 문제는 좀 수학적인 지식이 있어야 풀수가 있다. 그 이유는 데이터의 크기가 조단위이고 나머지 1억인점을 생각하면 일반적인 모듈러 연산을 이용해도 시간 초과가 나올것이다. 파이썬의 초당 처리속도는 2000만정도라고 생각하면 방법이 O(logN)방법 말고 없다. 조단위 라고 해도 1000이면 10번 조는 60번정도이면 처리가 가능해서  O(logN)방법으로 처리하는 법을 생각한다. 그 방법 중에 하나가 행렬 제곱으로 처리하는 방법이다.

위 공식을 보면 N은 N번째 피보나치 수의 결과값으로 보면 된다.  위 공식에 따르면 0을 제외하고는 [[1, 1], [1, 0]]을 N번 제곱한 후에 (0,1)인덱스 값과 (1, 0)인덱스  값만 구하면된다.  그럼 행렬 제곱을 O(logN)처리하는 방법은 아래 사이트 문제 풀어보면 알수 있어서 밑에 사이트 참조하면된다.

https://jih3508.tistory.com/72

[BAEKJOON] 10830 행렬 제곱

 위 사이트 코드의 행렬 부분만 수정만 하면되서 위에 문제 제대로 이해하면 Gold2 문제치고는 어려움이 크게 없다고 생각한다.

Code

Python

def mul_matrix(expo):
    if expo == 1: return matrix  
    result = mul_matrix(expo // 2)
    if (expo %  2) == 1: return mul(mul(result, result), matrix)
    else: return mul(result, result)

def mul(matrix1, matrix2):
    result = [[0] * size for _ in range(size)]
    for i in range(size):
        for j in range(size):
            for k in range(size):
                result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000000007
    return result

N  = int(input())
size = 2
matrix = [[1, 1], [1, 0]]
print(mul_matrix(N)[0][1] % 1000000007 if N > 0 else 0) # 0일때는 0을 출력해야한다.

Java

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

public class Main {
	
	static int size = 2;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		
		long[][] matrix = {{1, 1}, {1, 0}};
		
		System.out.println(N > 0 ? matrix_mul(matrix, N)[0][1]: 0);
		
	}
	
	public static long[][] matrix_mul(long[][] arrays, long expo){
		if (expo == 1) return arrays;
		
		long[][] result = matrix_mul(arrays, expo / 2);
		
		if(expo % 2 == 1) return mul(mul(result, result), arrays);
		else return mul(result, result);
	}
	
	
	public static long[][] mul(long[][] matrix1, long[][] matrix2){
		long[][] result = new long[size][size];
		
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				for(int k = 0; k < size; k++) {
					result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000000007; 
				}
				result[i][j] = result[i][j] % 1000000007;
			}
		}
		
		return result;
	}
		
}