24416

날짜 : 2022. . 

사용 언어 : python

 

문제

 

 

코드

import sys

def fib(n):
    if n == 1 or n == 2:
        global i
        i += 1
        return 1
    else: return fib(n-1) + fib(n-2)

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

i, j = 0, 0
t = int(sys.stdin.readline())
fib(t)
fibonacci(t)
print(i, j)

 

 

알게된 점

- 재귀와 DP의 코드실행 횟수를 직접적으로 비교해서 보여주는 문제였다.

- 일반 Python3로 실행했는데 시간초과가 떠서 pypy로 하니까 바로 정답이 나왔다.

 

 

참고 사이트

-