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

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

 

의사코드를 보고 피보나치 수를 구하는 2가지 함수를 만들고 코드1 코드2번 자리에 횟수를 기록하는 부분을 추가해주면 된다.

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int cnt1 = 0; // 재귀 호출 횟수 카운트

// 재귀 방식 피보나치 함수
long fib(int n) {
    if (n == 1 || n == 2) {
        cnt1++;
        return 1;
    }
    else {
        return (fib(n - 1) + fib(n - 2));
    }
}

// 동적 프로그래밍 방식 피보나치 함수
int fib2(int n) {
    vector<int> f(n + 1); // 배열 크기를 n + 1로 선언
    f[1] = f[2] = 1;
    int cnt2 = 0;

    // 피보나치 수열 계산 및 코드2 실행 횟수 카운트
    for (int i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
        cnt2++;
    }

    return cnt2; // 코드2 실행 횟수 반환
}

int main() {
    int n;
    cin >> n;

    fib(n); // 재귀 피보나치 계산
    int cnt2 = fib2(n); // 동적 프로그래밍 피보나치 계산

    cout << cnt1 << " " << cnt2 << endl;

    return 0;
}