1003 피보나치 함수

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

1003번: 피보나치 함수

T= int(input())
#for _ in range(T):
#   
def fibonum(n):
    zero = [1,0,1]
    one = [0,1,1]
    #n=3 부터 해야하므로 
    if len(zero) <=n:
        for i in range(len(zero),n+1):
            zero.append(zero[i-2]+zero[i-1])
            one.append(one[i-2]+one[i-1])
    return zero[n],one[n]
    
    
for i in range(T):
    n=int(input())
    a,b = fibonum(n)
    print(a, b)
    
    
    

 
"""def fibo(n):
    global onecnt, zerocnt
    if n==0:
        zerocnt+=1
        return(0)
    elif n==1:
        onecnt+=1
        return(1)
    return fibo(n-1)+fibo(n-2)
    

for _ in range(T):
    onecnt=0
    zerocnt=0
    n=int(input())
    fibo(n)
    print(zerocnt, onecnt)
    """

 

맨첨에 재귀로했다가 틀림 시간초과로

 

찾아보니 0과 1의 수도 피보나치수로 표현가능 

 

dp는 디피라는 것을 알아차리고 어떻해서든 규칙을 찾는게 중요!!