[백준] 24416 알고리즘 수업 - 피보나치 수 1 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/24416
• 피보나치 수를 직접 재귀를 구현해서 풀면 시간초과가 뜬다.
• n에 해당하는 피보나치 수를 재귀로 구한 값과 재귀가 호출된 횟수는 같아서 dp로 얻은 값을 리턴함

n = int(input())

def dp_fibo(n):
    dp = [1, 1]
    cnt = 0
    for i in range(2, n):
        dp.append(dp[i-2]+dp[i-1])
        cnt += 1

    return print(dp[n-1], cnt)

dp_fibo(n)