January 1, 2023

10870번: 피보나치 수 5

문제 요약

• n이 주어질 때, n번째 피보나치 수 출력
• 0 ≤ n ≤ 20
• 시간 제한 1초

풀이

n = int(input())

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

print(fibonacci(n))

• 재귀를 이용하여 피보나치 수를 계산

시간 복잡도 분석

• O(n)
• n의 크기에 비례