[백준 10870] 피보나치 수 5 문제 풀이- 파이썬 python

 

0. 자세한 설명은 YouTube 영상으로

1. 재귀함수만 사용한 풀이

# ver 1
def fib(num):
    # 2. 탈출 조건
    if num < 2:
        return num

    # 1. 기본 동작
    return fib(num - 1) + fib(num - 2)
num = int(input())
print(fib(num))

2. 재귀함수 + DP 풀이

# ver 2
def fib(num):
    # 2. 탈출 조건
    if dp[num] == -1: # 한번도 연산된 적이 없다면
        dp[num] = fib(num - 1) + fib(num - 2)

    # 1. 기본 동작
    return dp[num]
num = int(input())
dp = [-1] * 100
dp[0] = 0
dp[1] = 1
print(fib(num))

 

 

3. DP 배열만 사용한 풀이

# ver 3
num = int(input())
dp = [0] * 100
dp[1] = 1
for i in range(2, num + 1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[num])