[파이썬] 백준 2748 : 피보나치 수 2

[파이썬] 백준 2748 : 피보나치 수 2

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

2748번: 피보나치 수 2

브론즈 1

수학, DP

---

접근

다이나믹 프로그래밍의 기본적인 문제.

보톰업 방식은 반복문을 이용해 작은 것부터 큰 수를 처리한다.

피보나치 수의 1, 2번째 수는 1이므로 미리 두 개를 할당하고 난 후에 3번째 값부터 반복문을 사용하면 쉽게 작성할 수 있다.

 

코드

 

import sys; input = sys.stdin.readline
N = int(input())
dp = [0]*90
dp[0], dp[1] = 1, 1
for i in range(2, N):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[N-1])

또는

import sys; input = sys.stdin.readline
N = int(input())
dp = [0]*91
dp[1], dp[2] = 1, 1
for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[N])

 

문제 조건에 N은 90보다 작거나 같은 자연수라고 했으므로 미리 그 범위만큼 리스트로 메모리제이션을 해둔다.

계산한 결과를 곧바로 리스트에 저장하기 때문에 중복되는 계산을 없애고 이전에 계산했던 값을 바로 불러올 수 있다.