[분할정복/DP] 백준 15624 피보나치 수 7 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

15624번: 피보나치 수 7

 

 

 

2. 문제 풀이

 짧은 시간 제한(1초) 내에 피보나치 수를 구해야 합니다.

 

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

 이를 위해서는 분할정복 또는 DP를 이용해야 합니다. 여기서는 피보나치 6에서 사용했던 분할 정복을 이용했습니다. 해당 방식에 대한 설명과 코드는 위 링크에 기재되어 있습니다.

 

 

 

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가 홀수인 경우

if N == 0:
    print(0)
else:
    result = power(matrix, N)

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

 피보나치 수 6과 달리, 피보나치 수 7은 N이 0일 때 0을 출력해야 합니다.