피보나치 수를 빠르게 구하는 문제입니다. 이 문제는 행렬을 사용하여 풀 수 있는 문제입니다라고 단계별로 풀어보기에 적혀있습니다. 먼저 피보나치 수열의 정의를 살펴보겠습니다. \(F_n=F_{n-1}+F_{n-2}\)로 주어져있으며, \(F_{n+1}=F_n+F_{n-1}\)로도 쓸 수 있습니다. 후자의 식을 행렬의 곱으로 나타내보면 \(\begin{pmatrix}1&1\end{pmatrix}\begin{pmatrix}F_n\\F_{n-1}\end{pmatrix}=1\cdot F_n+1\cdot F_{n-1}=F_{n+1}\)가 됩니다. 왠지 왼쪽 1, 1 행렬 아래에 1, 0 행을 추가하고 싶네요. 이를 넣어보면 \(\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}F_n\\F_{n-1}\end{pmatrix}=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}\)가 됩니다. 뭔가 깔끔하고 점화식의 느낌이 납니다. 만들어보겠습니다.
이제 이 식을 두 번 적용시켜서 피보나치 수가 들어있는 행렬을 정사각행렬로 만들어보겠습니다.
\[\begin{align*} \begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix}&=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix}\\ &=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}1&1\\1&0\end{pmatrix}\\ &=\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n+1} \end{align*}\\ \therefore\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\]만들고 보니 결국 행렬의 거듭제곱이 되었습니다. 2748번: 피보나치 수 2과 같은 O(n)이 아닌 O(log n)으로 더 빠르게 구할 수 있게 되었습니다. 행렬의 거듭제곱은 10830번: 행렬 제곱과 같이 구하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-04-05 17:50:49 |