1003. 피보나치 (재귀함수와 dp 차이)

재귀함수로 구현했을 때보다 DP로 구현했을 때 시간이 훨씬 적게 소요된다.

<재귀함수>
def fibonacci(n):
        if n == 0:
            print("0")
            return 0
        elif n == 1:
            print("1")
            return 1
        else:
            return fibonacci(n‐1) + fibonacci(n‐2)

<DP>
import sys
t=int(sys.stdin.readline())    
for i in range(t):
    num=int(sys.stdin.readline())
    #피보나치
    zero=[1,0,1]
    one=[0,1,1]
    if num>=3:
        for j in range(2,num):
            zero.append(zero[j-1]+zero[j])
            one.append(one[j-1]+one[j])
    print(zero[num],one[num])