[11444] 피보나치 수 6

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

피보나치 문제다. 해당 문제 덕분에 피보나치수를 구하는 다양한 방법들 있다는 것을 알았다.

 

풀이

$$F_{m+n} = F_{m-1} F_{n} + F_{m} F_{n-1}$$

도가뉴 항등식을 이용하였다. 해당 수식을 정리하면 

 

$$F_{2n} = F_{n} (F_{n} + 2F_{n-1})$$

$$F_{2n+1} = F_{n}^2 + 2F_{n+1}^2$$

위와 같은 수식을 얻을 수 있다.

해당 수식을 이용하면 기존의 피보나치수를 계산하는 방법보다 훨씬 적은 수의 호출을 통해서 값을 구할 수 있다.

 

메모리 초과를 피하기 위해 딕셔너리를 이용하여 수를 담아내었다.

 

정답 코드