[BOJ] #2747 - 피보나치 수

2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ** 문제 유형 재귀 함수 ** 풀이 피보나치 수열의 점화식 재귀 함수를 이용해 문제를 풀 수 있는지 검토 N은 최대 45 재귀적 구현의 한계: 과도한 중복 호출 -> O(2^n) n = int(input()) a, b = 0, 1 while n > 0: a, b = b, a + b n -= 1 print(a) f(n) 0 1 1 2 3 a b a + b ... ... a b ... ... a b ... a b

2021.06.15