[백준] 24416 : 알고리즘 수업 - 피보나치 수 1

 

문제에서 말하는 대로 풀었는데 Python3으로 제출하니 시간초과가 나왔고,

PyPy3로는 정답판정이 나왔다.

n = int(input()) 

def recursive_fibo(x):
    global cnt_recursive
    if x==1 or x==2:
        cnt_recursive +=1
        return 1
    return recursive_fibo(x-1)+recursive_fibo(x-2)

def dp_fibo(x):
    global cnt_dp
    dp = [1]*(x+1)
    for i in range(3,x+1):
        dp[i] = dp[i-1]+dp[i-2]
        cnt_dp  += 1

cnt_recursive = 0
cnt_dp = 0

recursive_fibo(n)
dp_fibo(n)

print(cnt_recursive, cnt_dp)

 

이렇게 넘기기엔 영 찝찝해서 다른 풀이를 찾아봤다.

 

재귀함수로 피보나치 수열을 풀었을 경우에는 피보나치수만큼 함수가 호출되기 때문에

dp로 피보나치수를 구하고 그냥 출력만 해줘도 정답판정에는 아무런 문제가 없었다. 

 

def dp_fibo(x):
    global cnt_dp
    dp = [1]*(x+1)
    for i in range(3,x+1):
        dp[i] = dp[i-1]+dp[i-2]
        cnt_dp  += 1
    return dp[x]

n = int(input()) 

cnt_dp = 0

print(dp_fibo(n), cnt_dp)