python-algorithm
백준 4150 피보나치 수
무적김두칠
2022. 10. 31. 17:53
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
반응형