백준 1003 피보나치 함수 (다이나믹 프로그래밍 / 파이썬)

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

<시간 초과 코드>

import sys
T = int(sys.stdin.readline())
lst = [0, 0]
def fibbonacci(lst, n):
    if n == 0:
        lst[0] +=1
        return 0
    elif n == 1:
        lst[1] += 1
        return 1
    else:
        return fibbonacci(lst, n - 1) + fibbonacci(lst, n - 2)
for i in range(T):
    fibbonacci(lst, int(sys.stdin.readline()))
    print(lst[0], lst[1])
    lst = [0,0]

내 방법: list를 집어넣어서 one, zero가 나올 때마다 리스트 값을 증가시켜준다.

-> 이렇게 피보나치를 재귀로 하게 되었을 경우,

우리는 T만큼 같은 동작을 반복하므로 앞에서 이미 결괏값이 나왔을 때 이를 참조하지 못하고 처음부터 다시 for문을 돌림

숫자가 커지게 되었을 때 피보나치 함수는 그만큼 많아지기 때문에 시간이 장난 아니게 커진다.

따라서 이미 결과가 나온 값은 더 이상 계산할 필요가 없도록 코드를 짜 주어야 한다.

 

<정답 코드>

import sys
input = sys.stdin.readline
zero = [1, 0, 1]
one = [0, 1, 1]
def fibbonacci(n):
    length = len(zero)
    if  n >= length:
        for i in range(length, n + 1):
            zero.append(zero[i - 1] + zero[i - 2])
            one.append(one[i - 1] + one[i - 2])
    print('{} {}'.format(zero[n], one[n]))
T = int(input())
for i in range(T):
    fibbonacci(int(sys.stdin.readline()))

이 코드에서 zero, one 리스트는 각각 0,1,2에 따른 one,zero의 호출값을 풀어놓은 것이다.

만일 n이 이 배열의 크기보다 크면 그 때부터 배열을 늘려가주면 된다.

이미 전 과정에서 리스트가 채워진 상태고 이를 참고만 하면 된다면 시간복잡도는 놀랍도록 줄어들 것이다.

(이렇게 하면 n에 26을 넣었을 때 연산도 26번만 하면 됨 / 이전에는 2^26번은 해야했을 것..)

 

재귀를 쓰지 않는 피보나치 계산법을 잘 알고 있자..