백준 11444 - 피보나치 수열 | Notion

피보나치 공식
- $\mathrm{ F_{n + 2} } = \mathrm{ F_{n + 1} } + \mathrm{ F_n }$
위 공식을 행렬 꼴로 바꿔보자
F라는 방정식에 대해 n번째 값을 구하기 위해 Ax = b 꼴로 만드려고 한다! → 그러기 위해 x인 $\begin{pmatrix} \mathrm{ F_{n + 1} } & \mathrm{ F_n } \end{pmatrix}^T$를 공통으로 둘 수 있는 하나의 간단한 식을 추가한다!

캡처2.PNG

이렇게 x를 공통인수로 하는 하나의 선형방정식을 얻을 수 있음
위 두 식을 결합해보자

캡처3.PNG

위와 같이 결합한 식을 일반화를 해보자! → 만약 $\begin{pmatrix} \mathrm{F_{n + 1}} & \mathrm{F_n} \end{pmatrix}^T$을 $\mathrm{u_n}$이라고 한다면 $\begin{pmatrix} \mathrm{F_{n + 2}} & \mathrm{F_{n + 1}} \end{pmatrix}^T$을 $\mathrm{u_{n + 1}}$로 표현 가능하다!

캡처4.PNG

이제 각각을 u에 대하여 변경한 후에 u벡터에 대해 풀 것이다!
- 초기값인 $\mathrm{ u_0 }$는 $\begin{pmatrix} 1 & 0 \end{pmatrix}^T$가 될 것입니다.

캡처5.PNG

그럼 $\mathrm{ u_1 }$부터 위 식에 맞게 나열해봅시다!

캡처6.PNG

이처럼 $\mathrm{u_n} = A^n * \mathrm{u_0}$으로 A라는 행렬의 n제곱으로 쉽게 구할 수 있습니다.

캡처7.PNG

이렇게 수식을 일반화하여 얻을 수 있습니다!