[DP] boj 10870. 피보나치 수 5

백준 10870. 피보나치 수

풀이 1 : 일반 반복문 구현

import sys
input = sys.stdin.readline

n = int(input())

first = 0
second = 1
result = 0
if n == 0:
    print(first)
elif n == 1:
    print(second)
else:
    for i in range(n-1):
        result = (first + second)
        first = second
        second = result
    print(result)

풀이 2 : 재귀

n <= 20이므로, 시간복잡도가 높지 않아 재귀로 풀어도 될 듯 하다.

import sys

input = sys.stdin.readline

def fib(n, one, two):
    if n == 0:
        return one
    elif n == 1:
        return two
    else:
        res = (one + two)
        one = two
        two = res
        return fib(n-1, one, two)
print(fib(int(input()),0, 1))

풀이 3 : DP

DP 유형의 가장 대표적인 예시인 피보나치를 다이나믹 프로그래밍으로 구현해봤다.

import sys

input = sys.stdin.readline

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

def fib(n):
    if n <= 1:
        return n
    elif dp[n] != 0:
        return dp[n]
    dp[n] = fib(n-1) + fib(n-2)
    return dp[n]
print(fib(n))