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

🔅코딩테스트 공부🔅/❗백준

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

윤무무 2023. 1. 10. 01:43

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

10870번: 피보나치 수 5

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

www.acmicpc.net

문제 : 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)