백준 2747번 피보나치 수 (DP)

DP를 배울 때, 가장 첫 번째로 등장하는 문제라고 할 수 있다.

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

2747번: 피보나치 수

 

피보나치 점화식은 문제에서 바로 주어지기 때문에, 딱히 설명하지는 않겠다.

 

포인트는 메모이제이션으로 변수 memo에 이전에 계산했던 값을 저장해놓기 위함이다.

피보나치 함수의 특성상 중복되어서 계산하는 부분이 많다.

예를들어 fib(5) = fib(4) + fib(3)인데, fib(4)를 구하기 위해서는 fib(3)+fib(2)를 구해야 한다.

이때, fib(3)이 중복되므로 미리 계산한 값을 memo에 넣어놓고 이 값이 0이 아니면 그 전에 계산했다는 의미이므로 return memo[n]을 하도록 한다.

 

<소스코드>

memo = [0] * 46

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

n = int(input())
print(fib(n))