[BaekJoon/C] No.24416 : 알고리즘 수업 - 피보나치 수 1

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

No.24416 문제

 

문제해석

 

여기서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인수열입니다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 합니다. => f[n]={0,1,1}

문제에서 제시한 재귀함수와 동적프로그램함수에 실행횟수를 계산해주는 변수를 추가해 작성합니다. 

 

 

소스코드 & 문제풀이

 

#include<stdio.h>

int f[41] = { 0,1,1 }; //0번째:0, 첫번째:1, 두번째:1
int cnt1 = 0; //피보나치 수 계산에서 실행 횟수를 셉니다
int cnt2 = 0;

int fib(int n) { //재귀함수
    if (n == 1 || n == 2) {
        cnt1++; 
        return 1;
    }
    else return (fib(n - 1) + fib(n - 2)); //n이 1,2가 아닐 시 자기자신을 호출해 계산합니다
}

int fibo(int n) { //동적 프로그래밍
    for (int i = 3; i <= n; i++) { //3번째 항부터 반복문을 실행합니다
        cnt2++;
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

int main() {
    int n;
    scanf("%d", &n);
    fib(n); //재귀함수를 호출합니다
    fibo(n); //동적프로그래밍을 호출합니다
    printf("%d %d", cnt1, cnt2); //각각의 함수 호출 횟수를 출력합니다 
    return 0;
}

 

 

예제 입출력 결과

 

예제1

예제2