✓

태그:

19. 분할 정복 CLASS 4 ESSENTIAL

Aⁿ이 n+1번째, n번째, n-1번째 피보나치 수로만 이루어진 정사각행렬이 있던데…

풀이 비스무리한거 보기

피보나치 수를 조금 더 빠르게 구하는 문제입니다. 그런데 풀고 보니 2749번 - 피보나치 수 3랑 풀이가 같아져버렸습니다 🤔🤔🤔

자세한 풀이는 2749번에서 보면 되고, 여기서는 간단한 풀이만 하겠습니다. 힌트와 같이 저런 성질을 만족하는 행렬이 있는데, 그것은 아래와 같습니다.

\[A=\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}F_{2}&F_{1}\\F_{1}&F_{0}\end{pmatrix}\\ A^{n}=\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}\]

이 행렬의 거듭제곱을 이용하여 값을 구하시면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-10 22:02:05

---