[백준 - 1003] 피보나치 함수 | Dynamic Programming | Python

 

 

cnt0 = {0:1, 1:0, 2:1}
cnt1 = {0:0, 1:1, 2:1}

def test(x):

    if x in cnt1:
        print("%d %d" % (cnt0[x], cnt1[x]))
        return

    for i in range(3, x+1):

            cnt0[i] = cnt0[i-1] + cnt0[i-2]
            cnt1[i] = cnt1[i-1] + cnt1[i-2]

            if x == i:
                print("%d %d" % (cnt0[x], cnt1[x]))
                return

c = int(input())

for _ in range(c):
    test(int(input()))

cnt0 과  cnt1의 딕셔너리를 따로 만들고 

각각이 피보나치 수열이라는 것을 깨닫고 진행하였다.

 

성공했지만 조금 더 효율적인 코드 작성을 위해 여러 검색을 했다.

 

T=int(input())
for i in range(T):
    N=int(input())
    zero=[1,0,1]
    one=[0,1,1]
    if N >= 3:
        for i in range(3, N+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print(zero[N], one[N])

리스트로 만들어도 충분했다. 그리고 이 코드가 전체적으로 간결하고 효율적인 코드인 것 같다.