[BOJ] 2748 : 피보나치 수 2 (Python3)

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

풀이

다이나믹 프로그래밍으로 해결한 피보나치 수열 문제.
DP는 큰 문제를 작은 문제로 쪼개어 해결하는 방법이다. 작은 문제를 풀다보면 반복하는 풀이가 생기는데, 그것을 매번 재계산하지 않고 값을 저장해두었다가 사용하는 방법이다.
때문에 재귀에 비해 시간 복잡도가 낮다.

소스코드

n = int(input())
arr = [0 for i in range(n+1)]
arr[1] = 1

for i in range(2, n+1):
	arr[i] = arr[i-1] + arr[i-2]

print(arr[n])