[CodeUp] 1916번 피보나치 수열 (Large)

링크 : https://codeup.kr/problem.php?id=1916

문제

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다.

1,1,2,3,5,8,13…

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

풀이

첫번째 풀이 - 시간초과

n = int(input())

def fibo_large(n):
    if n==1 or n==2:
        return 1
    return fibo_large(n-1)+fibo_large(n-2)

print(fibo_large(n) % 10009)

두번째 풀이

메모이제이션을 써야한다

def f(n):
    if n==0 or n==1:
        return n
    if l[n]==0:
        l[n] = f(n-1) + f(n-2)
    return l[n]

N = int(input())
l = [0]*201
print(f(N)%10009)