\(n\)번째 피보나치 수를 \(f(n)\) 이라고 했을 때, 이를 구하는 점화식은 \(f(n) = f(n-1) + f(n-2)\)입니다. (\(f(1) = f(2) = 1\)

\(n-1\)번째 피보나치 수는 \(f(n-1) = f(n-2) + f(n-3)\) 이고요

그럼 이것을 행렬로 나타낼 수 있습니다.

\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} \]

\[\begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix} \]

\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^{2} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix}\]

그럼, 앞의 행렬을 적절히 제곱을 한 다음에, 뒤의 행렬에 \(f(2)\)와 \(f(1)\)를 넣어주면 \(f(n)\)의 값을 빠르게 구할 수 있습니다.

와.. 행렬을 이용해서 f(n)을 구하는방법도 있군요.. 덕분에 중요한것 배워가네요

감사합니다!

덕분에 해결했습니다.. 감격 ㅠㅠ

행렬왕 백준형