[분할정복/DQ] 백준 11444 피보나치 수 6 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11444번: 피보나치 수 6

 

 

 

2. 문제 풀이

 n번째 피보나치 수를 구하는 문제입니다. 본래 피보나치 수열은 동적계획법 DP를 이용해서 효율적으로 구할 수 있지만, 이 문제에서는 최대 n이 1,000,000,000,000,000,000입니다.

 

 아주 큰 수의 피보나치를 빠르게 구하기 위해서는 분할정복을 이용한 '행렬의 거듭제곱'을 사용해야 합니다. 피보나치 규칙을 행렬로 나타내면 아래와 같습니다.

 

2022.05.10 - [Algorithm] - [분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python)

 결국 행렬의 거듭제곱 문제로 환원이 됩니다. 분할정복을 이용한 효율적인 행렬 제곱은 위 링크에서 찾아보실 수 있습니다.

 

 

 

3. 코드

# 입력
N = int(input())
matrix = [[1, 1], [1, 0]]

# 행렬 곱셈
def mul_matrix(mat1, mat2):
    res = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for z in range(2):
                # c11 = a11*b11 + a12*b21
                res[i][j] += mat1[i][z] * mat2[z][j] % 1000000007
    return res

# 분할정복
def power(a, b):
    if b == 1:  # b의 값이 1이 될 때까지 재귀
        return a
    else:
        tmp = power(a, b // 2)  # a^(b // 2)
        if b % 2 == 0:
            return mul_matrix(tmp, tmp)  # b가 짝수인 경우
        else:
            return mul_matrix(mul_matrix(tmp, tmp), a)  # b가 홀수인 경우
result = power(matrix, N)

# 출력
print(result[0][1] % 1000000007)

 백준 10830 행렬 제곱에서 사용했던 코드가 거의 그대로 쓰여졌습니다. 행렬 [[1, 1], [1, 0]]의 n제곱을 분할정복 기법으로 구한 후, (0, 1) 원소를 출력합니다.