본문 바로가기

Algorithm/[BOJ] - Python

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

 

문제에서 말하는 대로 풀었는데 Python3으로 제출하니 시간초과가 나왔고,

PyPy3로는 정답판정이 나왔다.

n = int(input())
def recursive_fibo(x):
global cnt_recursive
if x==1 or x==2:
cnt_recursive +=1
return 1
return recursive_fibo(x-1)+recursive_fibo(x-2)
def dp_fibo(x):
global cnt_dp
dp = [1]*(x+1)
for i in range(3,x+1):
dp[i] = dp[i-1]+dp[i-2]
cnt_dp += 1
cnt_recursive = 0
cnt_dp = 0
recursive_fibo(n)
dp_fibo(n)
print(cnt_recursive, cnt_dp)

 

이렇게 넘기기엔 영 찝찝해서 다른 풀이를 찾아봤다.

 

재귀함수로 피보나치 수열을 풀었을 경우에는 피보나치수만큼 함수가 호출되기 때문에

dp로 피보나치수를 구하고 그냥 출력만 해줘도 정답판정에는 아무런 문제가 없었다. 

 

def dp_fibo(x):
global cnt_dp
dp = [1]*(x+1)
for i in range(3,x+1):
dp[i] = dp[i-1]+dp[i-2]
cnt_dp += 1
return dp[x]
n = int(input())
cnt_dp = 0
print(dp_fibo(n), cnt_dp)