[Baekjoon 2748 / python / 브론즈1] 피보나치 수 2

x = int(input())

d = [0] * (x + 2)

d[1] = 1

d[2] = 1

for i in range(3, x + 1):

    d[i] = d[i-1] + d[i-2]

print(d[x])

 

간단한 DP 문제이다. 재귀함수로 구현하면 입력값이 90까지이기 때문에 메모리가 터져버린다.

 

x가 1, 2일 경우만 리스트에 등록해 둔 후 간단한 반복문을 돌리면 된다.

 

재귀 구현했을 경우 90이면 정말 컴퓨터가 터지기 직전까지 가는데 상향식 DP방식인 반복문으로 구현하면 대략 90번정도만 연산하면 되기 때문에 문제를 해결할 수 있다.