[백준] 10870 피보나치 수 5

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

10870번: 피보나치 수 5

 

피보나치 수열 문제이다. 피보나치 수열이란, 제 0항을 0,  제 1항을 1로 두고, 두번째 항부터 바로 앞의 두수를 더한 수로 놓는다.(F(2) = F(1) + F(0)). 피보나치 수를 상향식 분석하면 아래와 같다.

결론적으로 계속해서 f(n) = f(n-1) + f(n-2) 형태로 나아가는것을 볼 수 있다. 다만 주의해 줄 것이 있다. 피보나치 수열은 제 2항(F(2))부터 유효한 수열이다(앞의 두개의 항을 더해야 하므로) 그렇기 때문에,F(n)에서 n값이 0, 1인 경우에는 각각 0과 1을 반환해주어야한다. 코드는 아래와 같다.

 

재귀 1

def fibo(inp):
    if inp == 0:
        return 0
    elif inp == 1:
        return 1
    return fibo(inp - 1) + fibo(inp - 2)
    

if __name__ == "__main__":
    inp = int(input())
    print(fibo(inp))

재귀2(통상적인 피보니치 수열 풀이는 아님)

def fibo(start,end,count):
    if count == inp:
        return start
    return 0 + fibo(end,start + end, count + 1)
    

if __name__ == "__main__":
    inp = int(input())
    print(fibo(0,1,0))