백준 1003번 피보나치 파이썬 (python code)

난이도: 실버3
번호: 1003번

 

동적할당을 통해 피보나치수열을 빠르게 계산하는 문제이다.

시간이 0.25초로 매우 짧아서 실제 이론적 피보나치 수열을 구현하면 시간초과에 걸린다.

 

시간초과 코드: (피보나치 준 구현)

from sys import stdin


def check(num):
    global answer0, answer1
    if num==0:
        answer0 +=1
        return
    elif num==1:
        answer1 +=1
        return
    else:
        check(num-1)
        check(num-2)

T = int(stdin.readline().rstrip())
case=[int(stdin.readline().rstrip()) for _ in range(T)]
for i in range(T):
    answer0, answer1=0,0
    check(case[i])
    print("{} {}".format(answer0,answer1))

 

단순 덧셈을통한 계산 (72ms)

from sys import stdin


T = int(stdin.readline().rstrip())
case=[int(stdin.readline().rstrip()) for _ in range(T)]
num0=[1,0]
num1=[0,1]
for i in range(2,41):
    num0.append(num0[i-1]+num0[i-2])
    num1.append(num1[i - 1] + num1[i - 2])
for i in range(T):
    print("{} {}".format(num0[case[i]],num1[case[i]]))