02749번 피보나치 수 3

Problem link: https://www.acmicpc.net/problem/2749

Keywords: Divide and conquer

단지 멍청하게 외우고 있는 것인지, 진정 지성이 발휘되어 풀이가 떠오른 것인지, 혹은 그것을 구분할 필요조차 없는 것인지 모르겠다. 어쩃든 문제를 보는 순간 바로 행렬의 거듭제곱을 이용한 풀이 방법이 떠올랐다.

피보나치 점회식을 행렬로 적어보면 아래와 같다.

\[\left[ { \begin{array}{c} F_{n+2} \\ F_{n+1} \\ \end{array} } \right] = \left[ { \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} } \right] \left[ { \begin{array}{c} F_{n+1} \\ F_{n} \\ \end{array} } \right]\]

따라서, 아래와 같이 일반화 할 수 있고, 행렬의 거듭제곱만 분할정복으로 잘 구해주면 풀이를 얻을 수 있다.

\[\left[ { \begin{array}{c} F_{n} \\ F_{n-1} \\ \end{array} } \right] = \left[ { \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} } \right]^{n-1} \left[ { \begin{array}{c} F_{1} \\ F_{0} \\ \end{array} } \right]\]

솔루션은 여기 에서 확인할 수 있다.