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

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

2021. 5. 31. 14:52ㆍdev

10826번: 피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

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

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

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)

JEEYOUNG.ME