[백준/Python] 2748:피보나치 수 2

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

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

print(func(n))

시간초과가 난다.

캐싱을 안해서 오래걸리고, 시간복잡도도 엄청 높기에 시간초과가 나는 것이다,

우리는 중간저장인 캐싱을 사용해야한다.

타뷸레이션

n=int(input())

cache = [0] * 100
for i in range(100):
    if i==0:
        cache[i]= 0
    if i==1:
        cache[i]= 1
    else:
        cache[i]= cache[i-1] + cache[i-2]

print(cache[n])