[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)

 

2748번: 피보나치 수 2

 

<내 코드>

n = int(input())
memo = [0 for i in range(n+1)]
memo[1] = 1
for i in range(2, n+1):
    memo[i] = memo[i-1]+memo[i-2]

print(memo[-1])

처음에 재귀호출을 통해 풀었을 때, 예상대로 시간초과가 났다. 

Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.