[Python] 백준 24416 알고리즘 수업 - 피보나치 수 1

 

문제 분석

• 재귀 / 동적 함수 호출 횟수 출력

 

정답 코드

1차 - 실패.. 어떻게 return이 있는데 함수 호출을 하면서 또 함수 호출된 횟수에 대해서 return을 할 수 있지?

import sys
input = sys.stdin.readline

n = int(input())

# 피보나치 재귀 호출
def fib(n, cnt_rev):
    cnt_rev += 1
    if (n == 1 or n == 2):
        return 1
    else :
        return fib(n-1) + fib(n-2)

# 피보나치 dp
def fibonacci(n, cnt_dp) :
    cnt_dp += 1
    if n <= 2 :
        return 1
    f = [0] * (n+1) # 0부터 n까지의 배열 생성
    f[1] = f[2] = 1
    for i in range(3, n+1) :
        f[i] = f[i-1] + f[i-2]
    return f[n]

fib(n, 0)
fibonacci(n, 0)

 

다른 사람 코드 1

구현하고 구하는게 아니라..

def fib(n):
    f = [0] * (n+1)
    f[1] = f[2] = 1
    for i in range(3,n+1):
        f[i] = f[i-1]+f[i-2]
    return f[n]
    
def fibonacci(n):
    return n-2

n = int(input())
print(fib(n), fibonacci(n))