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

#include <stdio.h>

long long int n;

long long int getResult(long long int s1, long long int s2, int cnt) {
	
	if (cnt > n) {
		return (s1 % 10009 + s2 % 10009) % 10009;
	}
	else {

		long long int a = s2 % 10009;
		long long int b = (s1 + s2) % 10009;

		getResult(a, b, cnt + 1);
	}
}


int main(){
	
	scanf("%lld", &n);

	if (n == 1)
		printf("1\n");
	else
		printf("%lld\n", getResult(0, 1, 3));
		

	return 0;
}

아래 코드는 더 간결한 풀이법이다

#include <stdio.h>

int memo[201];

int f(int k)
{
    if (memo[k]) return memo[k];
    if (k <= 2) return 1;    
    return memo[k] = ( f(k-1) + f(k-2) ) % 10009;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", f(n));

    return 0;
}