[백준2749번] 피보나치 수 3 / Python3

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1000

예제 출력 1

228875

나의 풀이

이 문제는 분할정복 단계에서 밑에 나오는 힌트인 행렬 곱셈을 응용해 피보나치 수를 구하는 문제를 보고 문제를 접근하였다. 이 힌트를 보니 피보나치를 행렬로 표현하고 어느 일정한 수를 계속 곱해나가면 피보나치 수를 구할 수 있겠다는 생각을 했고 우선 노트에 끄적여보았는데 바로 규칙을 찾아내서 쉽게 풀 수 있었다.

위의 식을 보면 x를 구함으로써 피보나치를 구할 수 있다. 피보나치의 순서로만 나타내면 아래와 같다.

|0 1|  |2 3|  |4 5|
|2 3|  |4 5|  |6 7| ...

실제로 피보나치를 계산해보면 아래와 같다.

따라서 n번째 피보나치 수를 구하기 위해서는 처음 (0,1,2,3)번째의 수들을 가지고 있는 [[0,1],[1,2]]에 n을 2로 나눈 수 만큼 [[1,1],[1,2]]를 곱해주고나서 [0][n%2]인덱스의 값을 가져오면 된다.

그리고 거듭제곱을 빠르게 하기위해서 행렬 제곱에서 사용한 분할정복으로 푼 코드를 응용하였다.

코드

# 2749번 피보나치 수 3

# 행렬 제곱
def mul(n,matrix1,matrix2):
    result = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000000

    return result

# 2분할
def devide(n,b,matrix):
    if b == 1:
        return matrix
    elif b == 2:
        return mul(n,matrix,matrix)
    else:
        tmp = devide(n,b//2,matrix)
        if b%2 == 0:
            return mul(n,tmp,tmp)
        else:
            return mul(n,mul(n,tmp,tmp),matrix)

# 입력
n = int(input())

# 기본 피보나치 행렬
fibo = [[0,1],
        [1,2]]
# 제곱 행렬
mul_mat = [[1,1],
           [1,2]]

# 제곱 수
b = n // 2

if b==0:
    print(fibo[0][n%2])
else:
    sq_mat = devide(2,b,mul_mat)
    result = mul(2,fibo,sq_mat)
    print(result[0][n%2] % 1000000)