[C++] 백준 24416. 알고리즘 수업 - 피보나치 수1

🌽 문제

🥕 입출력

🥔 풀이

의사코드를 본인의 언어로 변환한 뒤, 코드1과 코드2부분에
실행 횟수를 카운트하는 코드만 추가하면 된다.

피보나치 수를 계산할 때 재귀보다 DP의 효율이 얼마나 더 좋은지 체감할 수 있다.

🥬 코드

#include <iostream>
using namespace std;

int cnt1 = 0;
int cnt2 = 0;
int f[41];

int fib1(int n) {
    if (n <= 2) {
        cnt1++;
        return 1;
    }
    return (fib1(n - 1) + fib1(n - 2));
}

void fib2(int n) {
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= n; i++) {
        cnt2++;
        f[i] = f[i - 1] + f[i - 2];
    }
}

int main() {
    int n;
    cin >> n;
    fib1(n);
    fib2(n);
    cout << cnt1 << " " << cnt2;
    return 0;
}

🥜 채점