동적 프로그래밍 : 피보나치 수 2(백준 2748번)

▶ 문제 : https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

##### 문제 #####
# 피보나치 수는 0과 1로 시작한다. 
# 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 
# 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
# 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
# n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

##### 출력 #####
# 첫째 줄에 n번째 피보나치 수를 출력한다.

 

▶ 접근 방법

동적 프로그래밍의 기본 예제였다.
메모리 사용을 최소로 하려면 어떻게 해야 할지 고민해보았다.

 

▶ 풀이 코드

import sys

# 메모리 사용을 최소로 하는 방법
N = int(sys.stdin.readline().rstrip())

def fibo(N):
    current = 1
    previous = 0

    # 반복적으로 위 변수들을 업데이트한다. 
    for _ in range(1, N):
        current, previous = current + previous, current

    return current

print(fibo(N))


# 메모리를 사용하는 방법
memo = [0 for i in range(N+1)]

def memoization_fibo(N):
    memo[0] = 0
    memo[1] = 1

    if N < 2:
        return memo[N]
    
    for i in range(2, N + 1) :
        memo[i] = memo[i - 2] + memo[i - 1]

    return memo[N]

print(memoization_fibo(N))
print(memo)

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?