

문제에서 말하는 대로 풀었는데 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)
'Algorithm > [BOJ] - Python' 카테고리의 다른 글
[백준] 12865 : 평범한 배낭 python (0) | 2023.09.28 |
---|---|
[백준] 1149 : RGB거리 python (1) | 2023.09.28 |
[백준] 16928 : 뱀과 사다리 게임 python (0) | 2023.09.24 |
[백준] 1012 : 유기농 배추 python (0) | 2023.09.24 |
[백준] 12015 : 가장 긴 증가하는 부분 수열 2 python (0) | 2023.09.23 |