[파이썬] 백준 10870번 피보나치 수 5 (5월6일)

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

10870번: 피보나치 수 5

 

 

피보나치수 를 재귀함수를 써서 풀어야 한다는 생각에 뭔가 많이 어려울것 같았는데 의외로 답은 이미 문제에서 주어졌었다. 주요 공식은 바로 Fn = Fn-1 + Fn-2 (n>=2)

 

쉽게 말해서 현재 수의 앞자리 두자리를 더한 숫자의 합이 피보나치 수의 결과값이 되는것이다

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

예를들어 f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2 인데

 

//////////////////////////////////////////////////

def fibo(n):

 

if n < 2:

 

    return n

 

else:

 

    return fibo(n-1) + fibo(n-2)

 

number = int(input())

print(fibo(number))

/////////////////////////////////////////////////

 

설명을 조금 덧붙이자면 조건문을 달아서 처음 if 문에 충족하면 재귀함수(recursive)를 탈출하는 형식이다.

여기서 어려운 점은 fibo 5를 알기 위해선 fibo 4, 3, 2, 1 을 전부 알아야 한다는것 이다. 

fibo 4 + fibo 3 이 되는걸 알수있고,

 

fibo 1은 첫번째 if 문에서 1이라는 결과를 가지고

fibo 2도 1 

fibo 3은 1 + 1 을 한 2

fibo 4 는 2 + 1 을 한 3

fibo 5 는 3 + 2를 한 5가 되겠다.