https://www.acmicpc.net/problem/4150
4150번: 피보나치 수
피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
|
import sys
sys.setrecursionlimit(10**6)
def sol(fibo,n):
if n in fibo:
return fibo[n]
else:
fibo[n]= sol(fibo, n-1)+sol(fibo,n-2)
return fibo[n]
fibo={0:0,1:1}
n=int(input())
print(sol(fibo,n))
|
cs |
단순 재귀로 풀면 에러가 나니 메모이제이션을 구현하도록합시다
If you think this problem as just recursion ,
You gonna see ERROR,
So make a code with memoization
반응형
'python-algorithm' 카테고리의 다른 글
| 백준 16916 부분 문자열 (0) | 2022.11.01 |
|---|---|
| 백준 3035 스캐너 (0) | 2022.10.31 |
| 백준 16172 나는 친구가 적다 (Large) (0) | 2022.10.31 |
| 백준 14405 피카츄 (0) | 2022.10.31 |
| 백준 2033 반올림 (0) | 2022.10.31 |
댓글