BOJ 11524 - Immortal Porpoises

image.png

단순히 피보나치 수를 구하는 문제이다.

$f(n)=f(n-1)+f(n-2)$이므로

$$ \begin{pmatrix} f(n)+f(n-1) \\ f(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} $$

임을 이용하여 행렬 거듭제곱을 이용해 풀면 된다.

Tags:

Categories:

Updated:

Comments