[백준] 10870번 피보나치 수 5(with python)

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

문제 : n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

1. 내가 작성한 코드

n = int(input())

x,y,z = 0,1,0

for i in range(0,n+1):
  if i == 0:
    z = 0

  elif i == 1:
    z = 1

  elif i == 2:
    z = x + y

  else :
    x = y
    y = z
    z = x + y
    
print(z)

피보나치는 재귀함수를 활용하는 대표적인 .. 문제인데.. 수학시간에 열심히 배운 건데..

왜 for문이랑 if문 반복해서 저렇게 더럽게 ?! 만든 거지?! 

 

활용할 수 있을 때 사용하기 ❗재.귀.함.수 

 

2. 모범답안

 

재귀 이용

def repeat(n) :
  if n <= 1:
    return n
  return repeat(n-1) + repeat(n-2)

n = int(input())
print(repeat(n))

 

DP 이용

n = int(input())

dp = [i for i in range(n+1)]

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