[baekjoon] 백준 10870번(파이썬): 피보나치 수 5

문제

10870번: 피보나치 수 5

알고리즘

- 1, 2, 3을 통해 만들 수 있는 경우의 수를 찾는 것이기 때문에 1, 2, 3의 경우의 수를 구하고 그것을 재귀 함수를 통해 입력받은 수를 만들 수 있는 경우의 수를 찾는다.

- 피보나치 수 0번째는 0이기 때문에 0을 리턴

- 피보나치 수 1번째는 1이기 때문에 1을 리턴

- 그 외 2보다 크거나 같은 피보나치 수는 앞 피보나치 수의 합이므로 재귀 호출을 통해 구해서 합을 구한다.

코드

import sys


def dp(m):
    # 피보나치 수가 0일 때 0을 리턴
    if m == 0:
        return 0

    # 피보나치 수가 1일 때 1을 리턴
    elif m == 1:
        return 1

    # 피보나치가 2 이상일 경우에는 바로 앞 두 피보나치를 재귀 호출로 구해 합한다.
    else:
        return dp(m - 1) + dp(m - 2)


n = int(sys.stdin.readline())
print(dp(n))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법