[알고리즘] 백준 2747 피보나치 수

 

def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

n = int(input())
print(fibo(n))

이 코드의 시간복잡도는 O(2^n)으로 너무 크다 시간초과 오류

 

n = int(input())
a, b = 0, 1

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

print(a)

단순 반복문으로 해결