[백준] 24416 파이썬(python) : 알고리즘 수업 - 피보나치 수 1

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

 

 

import sys
n = int(sys.stdin.readline())
def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

def fibo_dp(n):
    cnt = 0 #1
    dp = [0]*41 #2
    dp[1], dp[2] = 1, 1 #3
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2] #4
        cnt += 1 #5
    return cnt
print(fibo(n), fibo_dp(n))

 

#1 : 숫자를 세어줄 변수

#2 : dp테이블 초기화 n의 최댓값은 40이므로 41로 설정

#3 : 피보나치 수열의 점화식에 따라 1, 2를 지정

#4 : 점화식

#5 : 한번 진행할때마다 cnt +1

 

 

피보나치 수를 구할때 dp가 재귀함수보다 훨씬 빠르다는것을 알 수 있는 문제였다.