문제

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net/problem/2749

  • 입력

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

  • 출력

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

최종 코드

처음엔 그냥 반복문으로 구현해서 제출했는데 당연히 시간초과가 떴다. 아니 반복문이랑 재귀함수로 푸는 방법 말고는 모르는데 ㅠㅠ. 골드2 문제인 이유가 있었다.

바로 검색해보니까 행렬의 곱셈으로 피보나치 수열을 구하는 방법이 있었다. 행렬 곱셈을 활용한 풀이는 여기를 참고했고, 행렬의 곱셈은 이전에 풀었던 백준 10830번 행렬 제곱을 참고했다.

import sys

def mul_matrix(a, b):
    ret = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ret[i][j] += a[i][k] * b[k][j]
                ret[i][j] %= 1000000
    return ret

n = int(sys.stdin.readline())
res = [[1, 1], [1, 0]]
m = [[1, 1], [1, 0]]

while n:
    if n%2 == 1:
        res = mul_matrix(res, m)
    m = mul_matrix(m, m)
    n = n//2

print(res[1][1])

참고 사이트