링크 : https://www.acmicpc.net/problem/24416

1. 문제

2. 코드

import sys
input = sys.stdin.readline

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

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

N = int(input())
count1 = 1
count2 = 0

fib(N)
fibonacci(N)
print(count1, count2)

3. 의사코드 파이썬 코드 변환

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

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