코드업(CodeUp) - C 1916번 - (재귀함수) 피보나치 수열 (Large)

문제 :https://codeup.kr/problem.php?id=1916

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

 

문제 설명

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

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

 

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

 

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

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

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

금지 키워드 : while goto for

 

 

입력

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

출력

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

 

입력 예시

7

출력 예시

13

 

 

코드 : 

# include <stdio.h>

int n,arr[201];

int p(int a)
{
	if(arr[a])
		return arr[a];
	
	if(a < 3)
		return 1;
	
	
	return arr[a] = (p(a-2)+p(a-1))%10009;
	
	
}


int main()
{
	scanf("%d",&n);
	printf("%d",p(n));
	return 0;
}