https://www.acmicpc.net/problem/2748
def f(n):
if n == 0:
return 0
elif n == 1:
return 1
return f(n - 1) + f(n - 2)
print(f(int(input())))Í
25까지는 무사히 잘 나온다.
다만 입력을 90까지 늘렸는데 갑자기 무한루프가 도는 느낌이다.
f(90) 부터 계속 수많은 f(x)들을 호출하는데 캐싱을 하지 않은 상태이므로 f(88)을 호출하고 f(88)을 한번더 호출할 가능성이 있기 때문에 f를 호출 할 때 시간이 오래 걸린다. 이럴때 메모이제이션을 적용해야 한다.
count = 0
def f(n):
global count
count += 1
if n == 0:
return 0
elif n == 1:
return 1
return f(n-1) + f(n-2)
print(f(int(input())))
print(f'count: {count}')
# 초기값을 음수로 입력해주면 n번째 캐시가 음수가 있는여부를 새로 구한 문제인지 판단
cache = [-1] * 91
cache[0] = 0
cache[1] = 1
count = 0
def f(n):
global count
count += 1
if cache[n] == -1:
cache[n] = f(n - 1) + f(n - 2)
return cache[n]
print(f(int(input())))
print(f'count: {count}')
# 초기값을 음수로 입력해주면 n번째 캐시가 음수가 있는여부를 새로 구한 문제인지 판단
cache = [-1] * 91
cache[0] = 0
cache[1] = 1
count = 0
def f(n):
global count
count += 1
if cache[n] == -1:
cache[n] = f(n - 1) + f(n - 2)
return cache[n]
# if n == 0:
# return 0
# elif n == 1:
# return 1
# return f(n-1) + f(n-2)
print(f(int(input())))
# print(f'count: {count}')
N = int(input())
cache = [-1] * 91
cache[0] = 0
cache[1] = 1
for i in range(2, N + 1):
cache[i] = cache[i - 1] + cache[i - 2]
print(cache[N])