[Algorithm] CodeUp 1916 (재귀함수) 피보나치 수열 (Large)(python 파이썬)

1916 : (재귀함수) 피보나치 수열 (Large)

문제 설명

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

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 

피보나치 수열을 나열해 보면 다음과 같다.

1,1,2,3,5,8,13…
 
자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

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

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

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

자연수 N이 입력된다. (N은 200보다 같거나 작다.)

출력

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

입력 예시

7

출력 예시

13

풀이

※ 주의 : 시간초과 -> DP의 전형적인 문제로 판단하여 Memorization이 필요

※ Memorization에 대해서는 뒤에서 자세히 알아보자

def fibonacci(n):
  if n == 0 or n == 1:
    return n
  if l[n] == 0:
    l[n] = fibonacci(n-1) + fibonacci(n-2)
  return l[n]
  
N = int(input())
l = [0]*201
print(fibonacci(N)%10009)