[DP/동적계획법] 백준 10826 피보나치 수 4 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10826번: 피보나치 수 4

 

 

 

2. 문제 풀이

 N번째 피보나치 수를 구하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 동적계획법을 사용하면 쉽게 구할 수 있습니다.

 

 

3. 코드

N = int(input())

def calFibonacci(n):
    cache = [0, 1] #fibo(0) = 0, fibo(1) = 1
    for i in range(2, n+1):
        cache.append(cache[i-1] + cache[i-2])
    return cache

fibo = calFibonacci(N)
print(fibo[N])

 cache로 N번째 피보나치 수까지 차례차례 구해줍니다. 이전 계산값을 저장해두기 때문에, 빠르게 불러와서 해결할 수 있습니다.