[알고리즘 문제풀이] 피보나치 수

문제 제목 : 피보나치 수

문제 난이도 : 하

문제 유형 : 재귀함수, 구현

https://www.acmicpc.net/problem/2747
시간 제한 : 1초
메모리 제한 : 128MB

문제풀이 아이디어

1. 피보나치 수열의 점화식 활용
2. 재귀함수를 이용할 수 있는지 확인
   -> 문제에서 입력되는 n의 최대값은 45
   -> 피보나치 수열을 재귀함수를 이용하게 되면 시간 복잡도는 O(2^N)이므로 n이 45일 경우 python을 이용하여 연산할시 너무 오랜 시간이 걸린다.
   -> 재귀함수 이용 X
3. 기본적인 반복문을 사용하여 문제 해결 or DP(Dynamic Programming)사용하여 문제 해결

< 소스코드 >

# 재귀 함수 이용 (이 문제에서는 해결 x) -> 시간 초과
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(int(input())))

# 반복문 이용
n = int(input())

a, b = 0,1 

while n > 0:
    a, b = b, a + b
    n -= 1
    
print(a)