백준 10826: 피보나치 수 4 (DP)

10826번: 피보나치 수 4

일반적인 피보나치 수열문제. 

아래처럼 재귀로 풀었더니 시간초과가 났다. 

n = int(input())

def fibo(x):
  if x==0:
    return 0
  elif x==1:
    return 1
  else:
    return fibo(x-1) + fibo(x-2)

print("%d" % fibo(n))

재귀로 풀면 정수 x가 커질수록 연산시간이 그만큼 늘어나므로 시간초과가 발생한다

다이나믹 프로그래밍으로 풀이하고, 처음에 0과 1을 각각 x, y에 넣는다면 

1은 다시 x가 되고, 0+1이 y에 할당된다. 이를 n범위까지 반복해주면 된다. 

 

정답 코드

n = int(input())
x, y = 0, 1 
for i in range(n):
  x, y = y, x+y
print(x)