[python/파이썬] 백준 10870 피보나치 수 5

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

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

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

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

55

 

[문제 풀이]

 

재귀를 이용하기만 하면 되는 아주 쉬운 문제이다.

 

피보나치수열은 n번째 숫자가 n-1번째 숫자와 n-2번째 숫자의 합인 수열이다.

n이 주어졌을 때 n-1과 n-2가 존재해야 하기에 n>=2부터 성립한다.

***

n = 0 -> 0

n = 1 -> 1

***

 

예를 들어 10번째 숫자를 구한다고 한다면

0 1 (0+1) (1+1) (1+2) (2+3) (3+5) (5+8) (8+13) (13+21) (21+34=55)

55가 된다.

 

이걸 코드로 나타내면

fibo라는 함수를 하나 정의하고 매개변수는 정수인 n으로 한다

1보다 작거나 같은 경우 (0 or 1)는 각각 0과 1을 반환하고

그렇지 않은 경우는 fibo(n-1)+fibo(n-2)를 반환한다

 

다시 n=10일 때를 보면

-----------------1st-------------------

fibo(10)

-----------------2nd-------------------

fibo(9) + fibo(8)

-----------------3rd-------------------

fibo(8) + fibo(7) // fibo(7) + fibo(6)

----------------4th-------------------

fibo(7) + fibo(6) // fibo(6) + fibo(5) // fibo(6) + fibo(5) // fibo(5) +fibo(4)

----------------5th-------------------

fibo(6) + fibo(5) // fibo(5) +fibo(4) // fibo(5) +fibo(4) // fibo(4) +fibo(3) // fibo(5) +fibo(4) // fibo(4) +fibo(3) //

fibo(4) +fibo(3) // fibo(3)+ fibo(2)

----------------6th-------------------

fibo(5) + fibo(4) // fibo(4) + fibo(3) // fibo(4) + fibo(3) // fibo(3) + fibo(2) // fibo(4) + fibo(3) // fibo(3) + fibo(2) //

fibo(3) + fibo(2) // fibo(2) + fibo(1) // fibo(4) +fibo(3) // fibo(3) + fibo(2) // fibo(3) + fibo(2) // fibo(2) + fibo(1) //

fibo(3) + fibo(2) // fibo(2) + fibo(1) // fibo(2) + fibo(1) // fibo(1) + fibo(0)

......

이런 식으로 진행되고 결국에 fibo(0)과 fibo(1)에 도달하면 값이 나오게 된다.

 

 

[소스 코드]

 

n = int(input())

def fibo(n):
    if n<= 1:
        return n
    else:
        return fibo(n-1)+fibo(n-2)
print(fibo(n))