[ 백준 / C ] 24416번 : 알고리즘 수업 - 피보나치 수 1

24416

#include <stdio.h>
#include <stdlib.h>

// 재귀호출 피보나치 수 함수
int fib_r(int n, int *count){
    if((n == 1) || (n == 2)){
        (*count)++;
        return 1;   // 코드1
    }
    else{
        return (fib_r(n-1, count) + fib_r(n-2, count));
    }
}

// 동적 프로그래밍 피보나치 수 함수
int fib_d(int n, int*count){
    int *f=malloc(sizeof(int)*n);
    f[0]=1;
    f[1]=1;

    for(int i = 2; i < n; i++){
        (*count)++;
        f[i] = f[i-1] + f[i-2]; // 코드2
    }

    free(f);
    return f[n];
}

int main(void){
    // 숫자 입력
    int num = 0;
    scanf("%d", &num);

    int count_recursive = 0;
    int count_dp = 0;

    // 피보나치 
    fib_r(num, &count_recursive);
    fib_d(num, &count_dp);

    // 코드 1, 코드 2의 실행횟수 출력
    printf("%d %d", count_recursive, count_dp);

    return 0;
}