[백준 1003 피보나치 함수] PYTHON

 

fib(0)= fib(0)  1 0

fib(1)= fib(1)  0 1

fib(2)= fib(1) + fib(0)  1 1

fib(3)= fib(2) + fib(1) = fib(1) + fib(0) + fib(1)  1 2

fib(4)= fib(3) + fib(2) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) 2 3

위와 같이 피보나치 처럼 0과 1의 호출횟수가 fib(n-1) + fib(n-2)라는 것을 알 수 있다.

문제를 풀다 보니 어차피 진짜 피보나치 값인 fib(n),fib(n+1)과 동일하여 해당 방식으로 풀었으나 시간초과..

 

결국은 0과 1리스트를 만들어 풀었다.

from sys import stdin

zero_arr=[1,0,1]
one_arr=[0,1,1]
def sol(n):
    length=len(zero_arr)
    if (length<=n):
        for i in range(length,n+1):
                zero_arr.append(zero_arr[i-1]+zero_arr[i-2])
                one_arr.append(one_arr[i-1]+one_arr[i-2])
    print(zero_arr[n],one_arr[n])
if __name__ == "__main__":
    t=int(stdin.readline())
    for _ in range(t):
        tmp=int(stdin.readline())
        sol(tmp)

 CLEAR!!