백준 1003 - 피보나치 함수 (C언어)

백준을 접하고 푼 첫 실버문제이다.
DP등에 대한 기법에 전무한 상태였기 때문에 첫 시도에서 TLE가 나왔는데 다행이 다음 시행에서 성공했다.

문제

문제로 이동하기

해법 추론

문제에서 요구하는 것은 N번째 피보나치 수를 구하기 위해서 사용한 재귀함수(fibonacci)에서 fibonacci(0)과 fibonacci(1)을 얼마나 호출되었는기를 출력하는 것이다.

해법

$N$ 번째 피보나치 수의 0번 호출수를 fibo$[N][0]$, 1번 호출수를 fibo$[N][1]$라고 할 때

$N = 0$일때 fibo$[0][0] = 1$, fibo$[0][1] = 0$

$N = 1$일때 fibo$[1][0] = 0$, fibo$[1][0] = 1$이고

$N$번째 피보나치 수는 $N-1$번째 피보나치 수와 $N-2$번째 피보나치 수를 호출하므로

fibo$[N][0]$ = fibo$[N - 1][0]$ + fibo$[N - 2][0]$

fibo$[N][1]$ = fibo$[N - 1][1]$ + fibo$[N - 2][1]$이 성립한다.

이를 기반으로 코드를 짤 수 있다.

코드

#include <stdio.h>
 
void fibonacci(int N);
 
int main(void){
    int T;
    scanf("%d", &T);
 
    for(int i=0; i<T; i++){
        int N;
        scanf("%d", &N);
 
        fibonacci(N);
    }
}
 
void fibonacci(int N){
    if(N==0)
        printf("%d %d\n", 1, 0);
    else{   //N>0
        int fibo[N+1][2];
        fibo[0][0] = 1;
        fibo[0][1] = 0;
        fibo[1][0] = 0;
        fibo[1][1] = 1;
     
        for(int i=2; i<N+1; i++){
            fibo[i][0] = fibo[i-1][0] + fibo[i-2][0];
            fibo[i][1] = fibo[i-1][1] + fibo[i-2][1];
        }
        printf("%d %d\n", fibo[N][0], fibo[N][1]);
    }
}