백준 10870번 풀이

문제

피보나치 수열인데 이제 재귀함수맛 피보나치 수열이다. 살려주세요.

피보나치 수열

앞에놈 앞에놈 더하면 뒤에놈이 나오는 수열. 이렇게 말하면 뭔 소린지 모르겠다고? 그럼 예시를 보자.

0,1,1,2,3,5,8,13,21,37,…

1항이 0, 2항이 1일 때 3항은 0+1=1이다. 그리고 4항은? 2항이 1, 3항이 1이니까 1+1=2. 즉, 첫번째와 두번째를 제외한 피보나치 수열의 일반항은 F(n) = F(n-1) + F(n-2)가 된다.

풀이

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

기본 로직은 이거. 예시에는 0번째가 0이라고 나와있는데 왜 0번째부터인지는 모르겠지만 아무튼 그렇다. 0번째와 1번째가 각각 0, 1이니까 그것만 정의해주고 들어가면 된다.

import sys
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)
N = int(sys.stdin.readline())
print(fibonacci(N))

아, 입출력 빼먹으면 틀린다.