문제

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

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

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

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

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

입력

자연수 N이 입력된다.

입력 예시

7

출력

N번째 피보나치 수를 출력하되, 10,009를 나눈 나머지 값을 출력한다.

출력 예시

13

문제 풀이

피보나치 수열을 먼저 구하고, 해당 값을 저장해서 바로 불러오는 형식으로 진행하였다.
처음에 [] 로 구현했으나, 도저히 안되서 {} (dic)으로 사용하여 진행했다.

N = int(input())

memo = {0:0,1:1}

def fibo(n,memo):
    if n in memo:
        return memo[n]

    if n <= 1:
        return n
    
    memo[n] = fibo(n-1,memo) + fibo(n-2,memo)
    return memo[n]

print(fibo(N,memo)%10009)