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

---

풀이

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

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

단순 재귀 함수로 구현하면 틀린다.

재귀의 한계 때문이다.

필요 없는 계산은 하면 안된다.

호출이 되는 횟수는 깊이 들어갈수록 2배씩 늘어난다.

즉, 시간복잡도는 O(2^n) 이 된다.

 

def fibo(n):
    cache = [0] * (n+1)
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n+1):
        cache[i] = cache[i-1]+cache[i-2]
    return cache[n]

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

DP로 풀어도 시간 초과가 나온다.

 

따라서 for문을 통한 반복문으로 풀어야 한다.

 

n = int(input())
a, b = 0, 1
for i in range(n-1):
    a, b = b, a+b

print(b)