음.. 사실 이 문제는 피보나치수 구하는 데는 재귀함수보다 반복문이 훨씬 더 효율적이라는 걸 보여드리려고 만든 문제였는데..
재귀함수로도 풀리게끔 범위 줄여서 다시 채점할게요 감사합니다!
TLE가 나왔던 이유는
1. f(n) = f(n-1) + f(n-2)
2. 1의 f(n-1)을 계산하기 위해 f(n-2)랑 f(n-3)을 계산하고,
3. 1의 f(n-2)를 계산하기 위해 f(n-3)이랑 f(n-4)를 계산하고
4. 2의 f(n-2)를 계산하기 위해 f(n-3)이랑 f(n-4)를 계산하고 (3이랑 똑같은데 계산 또함)
...
그래서 결론은 f(n-1)이 1번, f(n-2)가 2번, f(n-3)을 3번, f(n-4)를 5번, f(n-5)가 8번, ... n이 커질수록 계산 횟수가 기하급수적으로 증가하게 됩니다
