24416 : 알고리즘 수업 - 피보나치 수 1

 

 

 

문제 해결 과정)

동적 계획법, 재귀 함수를 사용한 피보나치수열을 구하기 위한 호출 횟수를 구하면 되는 문제이고 의사 코드가 모두 주어져있기 때문에 난이도는 낮은 문제입니다.

그러나, 일반적인 python3로 채점을 진행하면 시간 초과가 발생하므로 pypy3로 채점을 진행했습니다.

 

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 27 00:01:49 2022
"""

global count_re
global count_by
count_re = 0
count_by = 0


def re_F(n):
    global count_re
    if(n == 1 or n == 2):
        count_re += 1
        return 1
    else:
        re_F(n-1)
        re_F(n-2)
    
    
def dy_F(n):
    global count_by
    num = [1, 1]
    for i in range(2,n):
        count_by += 1

n = int(input())
re_F(n)
dy_F(n)

print(count_re, end=' ')
print(count_by)