[BOJ] 백준 24416 알고리즘 수업 - 피보나치 수 1 (Swift)

문제

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

24416번: 알고리즘 수업 - 피보나치 수 1

풀이

단순히 문제만 보았을 때, 의사코드를 작성해서 직접 count를 해주는 것을 떠올릴 수 있습니다.
하지만, 재귀호출로 fib(40)을 호출한다면 어마어마하게 재귀호출을 하기 때문에 시간초과가 날 것입니다.

어떻게 코드1 횟수를 구할 수 있을까요?

단순히 생각해봅시다.
fibo(3)을 구하려면 fibo(2), fibo(1)이 필요합니다.
그렇다면 코드 1을 2번 호출을 하겠네요.

fibo(4)는 fibo(3), fibo(2)가 필요한데 fibo(3)은 2였으니깐 fibo(4)는 코드 1을 3번 호출

그렇다면 fibo(5)는 fibo(4), fibo(3)을 호출하는데 fibo(4)는 3번, fibo(3)은 2번.. 총 5번

호출 횟수(n)가 결국 피보나치 수열의 n번째 요소와 동일하게 이루고 있습니다.
당연하게도 코드 1 부분이 1을 return을 해주기 때문에 피보나치의 n번째 요소와 호출 횟수가 동일하지 않을까요?

따라서 코드 1번은 피보나치의 n번째 요소를 출력하면 될 것이고, 코드 2는 단순이 n - 2번 호출하게 되겠네요.

소스코드

후기

의사코드를 그대로 작성하면서 제대로 낚였던 문제였습니다..