bong-u/til

🏠 home 🐈 repository

백준 - 11444 : 피보나치 수 6 (G2)

수정일 : 2024-11-15

 1def multiply(m1, m2):
 2    result = [0, 0, 0, 0]
 3    result[0] = (m1[0]*m2[0] + m1[1]*m2[2]) % 1000000007
 4    result[1] = (m1[0]*m2[1] + m1[1]*m2[3]) % 1000000007
 5    result[2] = (m1[2]*m2[0] + m1[3]*m2[2]) % 1000000007
 6    result[3] = (m1[2]*m2[1] + m1[3]*m2[3]) % 1000000007
 7    return result
 8
 9def power(m, n):
10    if (n > 1):
11        m = power (m, n//2)
12
13        m = multiply (m, m)
14        if n % 2 == 1:
15            m = multiply(m, [1,1,1,0])
16    return m
17
18N = int(input())
19
20mat = power ([1,1,1,0], N)
21print (mat[1]%1000000007)

문제

  • n이 주어질 때 n번째 피보나치 수를 구하여라.

  • 이때 n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

  • TC

    • input

      1000

    • ouput

      517691607

해결방법

  • 행렬의 거듭제곱을 이용해여 피보나치 수를 구하였다
  • 공식은 다음과 같다

$$ \begin{bmatrix}F*{n+1} & F*{n} \\ F*{n} & F*{n-1} \ \end{bmatrix} = \begin{bmatrix}1&1 \\ 1&0 \\ \end{bmatrix} ^n$$

  • 홀수인 경우 한번 더 곱해주어야 한다는 것을 고려하여 분할 정복 방식으로 해결하였다