BOJ 2748번 : 피보나치 수 2 (Python/Bronze 1)

2748번: 피보나치 수 2

---

설명

n번째 피보나치 수를 출력하는 문제이다.

 

풀이

피보나치 수는 DP 알고리즘을 사용하는 것이 일반적이고 더 효율적이다.

 

Solution

방식 1. Bottom-up(하향식)

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*(n + 1)
dp[1] = 1

#bottom-up
def fibo(n):
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
    
print(fibo(n))

방식 2. Top-down(상향식)

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1)  

#Top-Down
def fibo(n):
    if n == 1 or n == 2:
        return 1
    if dp[n] == 0:
        dp[n] = fibo(n - 1) + fibo(n - 2)
    return dp[n]
    
print(fibo(n))