BOJ 1003번 :: 피보나치 함수

#작성 코드

#include <cstdio>

int T;	// 테스트 케이스의 개수 
int n;
long long int memo[41];
long long int fibo(int i){
	if( i==0 ){
		memo[i] = 0;
		return 0;	
	}
	if( i==1 ){
		memo[i] = 1;
		return 1;	
	} 
	
	if( memo[i]!=0 ) return memo[i];
	return memo[i]= fibo(i-1)+fibo(i-2);
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		if( n==0 )
			printf("1 0\n");		// fibo(0)에 대해서만 예외 출력 
		else
			printf("%d %d\n", fibo(n-1), fibo(n));
	} 
	return 0;
}

##

fibo(0) = 0

fibo(1) = 1

fibo(2) = fibo(1) + fibo(0) = 1

fibo(3) = fibo(2) + fibo(1) = 2*fibo(1) + fibo(0) = 2

fibo(4) = fibo(3) + fibo(2) = 3*fibo(1) + 2*fibo(0) = 3

...

fibo(n)을 호출했을 때 fibo(0)은 fibo(n-1)번 호출되고, fibo(1)은 fibo(n)번 호출됨을 알 수 있다.