1003)피보나치 함수

https://www.acmicpc.net/problem/1003

단순히 피보나치 수를 구하라는 문제는 아니다.

피보나치 수열은 점화식으로 정의ㅎㄹ 수 있는데 

대개 점화식으로 표현된 수열의 일반항은 경계 조건과 함께 재귀 함수로 표현할 수 있다.

문제는 n 번째 피보나치 수를 구하기 위해 1과 0을 몇 번이나 반환했는가 그 수를 세는 것이다.

n>=0일때 n번째 피보나치 수를 구하는 재귀 함수는 아래처럼 짤 수 있다.

int fibo(int n){
    if(n<=1) return n;
    else return fibo(n-1) + fibo(n-2);
}

f(3)일 때 0과 1이 몇 번이나 반환하는가를 확인하기 위해 콜트리를 작성해보자.

f(3)의 값을 구하기 위해 f(2)와 f(1)을 호출했고

f(2)의 값을 구하기 위해 f(1)과 f(0)을 호출했다.

f(0)를 한 번 호출해 0을 1회 리턴하고 f(1)을 두 번 호출해 1을 1회 리턴했다.

동적 계획법으로 피보나치 수를 구하는 함수를 다시 사용할 수 있는데 f(1)을 중복호출하는 것을 막아 오버헤드를 줄이기 위함이다.

3번째 피보나치 수에 0,1이 몇 번 쓰였는가 알기 위해 재귀 호출시 카운팅하지 않고 동적 계획법을 사용할 것이다.

f(0)일때 0을 1회 ,1을 0회 반환했고 f(1)일때 0을 0회 ,1을 1회 반환했다.

f(2)일 때 f(1),f(0)를 호출하므로 f(1)과 f(0)가 0,1을 반환한 횟수를 더하기만 하면 된다.

이를 저장하기 위한 자료 구조로 구조체 배열을 생각해볼 수 있다. 

f(2)가 0,1을 반환한 횟수를 구하기 위해 다음처럼 구조체 배열의 초기값을 사용하면 된다.

cntFibo[2].zero = cntFibo[0].zero + cntFibo[1].zero

cntFibo[2].one = cntFibo[0].one + cntFibo[1].one

#include<stdio.h>
typedef struct _CountFibo {
    int zero;
    int one;
}CountFibo;
 
int fibo(int n) {
    if (n <= 1) return n;
    else return fibo(n - 1) + fibo(n - 2);
}
 
int main() {
    int T; 
    int N;
    CountFibo cntFibo[41];
 
    cntFibo[0].zero = 1;
    cntFibo[0].one = 0;
    cntFibo[1].zero = 0;
    cntFibo[1].one = 1;
 
    for (int i = 2; i <= 40;i++) {
        cntFibo[i].zero = cntFibo[i-1].zero + cntFibo[i-2].zero;
        cntFibo[i].one = cntFibo[i-1].one + cntFibo[i-2].one;
    }
 
    scanf("%d",&T);
    
    for (int i = 0; i < T;i++) {
        scanf("%d",&N);
        printf("%d %d\n",cntFibo[N].zero, cntFibo[N].one);
    }
 
    return 0;
}