[백준] 1003번 피보나치 함수 (파이썬)

초기 코드 (실패)

가장 기본이 되는 재귀 형식으로 구현했더니 시간 초과 발생

import sys
input = sys.stdin.readline

def fibonacci(N):
    if N == 0:
        global zero
        zero += 1
        return 0
    elif N == 1:
        global one
        one += 1
        return 1
    else:
        return fibonacci(N-2) + fibonacci(N-1)

T = int(input())
for i in range(T):
    N = int(input())
    zero, one = 0, 0
    fibonacci(N)
    print (zero, one)

 

정답 코드 (성공)

핵심은 동적 프로그래밍의 메모이제이션 기법을 사용하는 것

이미 했던 계산을 반복 하는 경우, 기존에 계산 해두었던 값을 활용

 

import sys
input = sys.stdin.readline

zero = [1, 0, 1]
one = [0, 1, 1]

def fibonacci(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 (f"{zero[N]} {one[N]}")

T = int(input())
for i in range(T):
    N = int(input())
    fibonacci(N)