[dp/백준] 1003번: 피보나치 함수(2차)

-문제: https://www.acmicpc.net/problem/1003

 

-정답 풀이

0을 담는 배열과, 1을 담는 배열을 따로 초기화 한 후 이들끼리 피보나치 수열을 진행하면 된다고 생각했다

f(n)=f(n-1)+f(n-2)

 

점화식 값을 삽입하는 형태로 했는데, 틀린 답이 나왔다. python tutor를 돌려보니 길이가 22일 때, len(one),len(zero)의 값이 27이 되었으며, 틀린 답을 출력했다. 

length=len(zero)

if length <= n 부분을 입력하지 않아서 틀렸던 것 같은데, 아직 이유를 잘 모르겠다. 

 

t=int(input())
zero=[1,0,1]
one=[0,1,1]
for _ in range(t):
    n=int(input())
    length=len(zero)
    if length <= n:
        for i in range(length,n+1):
            zero.append(zero[i-2]+zero[i-1])
            one.append(one[i-1]+one[i-2])
        
    print(zero[n],one[n])

 

-틀린 풀이 

t=int(input())
zero=[1,0]
one=[0,1]
for _ in range(t):
    n=int(input())
    for i in range(2,n+1):
        zero.append(zero[i-2]+zero[i-1])
        one.append(one[i-1]+one[i-2])
        
    print(zero[n],one[n])