알고리즘

[BOJ] 10826. 피보나치 수 4 / 파이썬 풀이

besomilk 2022. 2. 7. 10:15

https://www.acmicpc.net/problem/10826

 

10826번: 피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

 

 

def fib(n):
    if(n==0):
        return 0
    elif(n==1):
        return 1
    else:
        return fib(n-1) + fib(n-2)
    
n = int(input())
print(fib(n))

런타임 에러 (RecursionError) / 시간초과

 

 

def fib(n):
    p = []
    p.append(0)
    p.append(1)
    
    for i in range(2, n+1):
        p.append( p[i-1] + p[i-2] )
        
    return p[n]
    
n = int(input())
print(fib(n))

재귀 사용하지 않고 구현, 성공

 

코드작성, 리뷰, 재작성 19'44"