11444번 피보나치 수 6

Fn = Fn+1 + Fn-2

그동안 했던 방식대로 top-down 또는 bottom-up으로 하면 안된다.

행렬을 이용해서 풀어야하는데 이해하기 더럽게 힘들다(바보라서 그런듯).

 

아무튼 피보나치 수를 행렬로 나타내면 이런 식이 나온다.

 

이 식을 정리하면 다음과 같다.

 

어떻게 이 식이 나오는 걸까? (참조 : https://blog.naver.com/skkong89/221490403921)

 

이 다음은 n을 짝수와 홀수로 나누어 계산해주면 된다 (분할 정렬 알고리즘에 따라 나누어질 수 없을때까지 나눈 후 계산하고 합치고 반복)