백준_python 1003번 피보나치 함수(다이나믹프로그래밍)

<문제 링크>

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

1003번: 피보나치 함수

 

 

 

<정답 코드>

def fibonacci(n) :
    zeros = [1, 0, 1]  
    ones = [0, 1, 1]
    if n >= 3:
        for i in range(2,n):
            zeros.append(zeros[i-1] + zeros[i])
            ones.append(ones[i-1] + ones[i])
    print(zeros[n], ones[n])
 
t = int(input())
 
for _ in range(t):
    n = int(input())
    fibonacci(n)

 

 

재귀로 접근하면 시간초과 또는 메모리 초과 발생