<백준> 24416

알고리즘 수업 - 피보나치 수1

문제

입력
첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

출력
코드1 코드2 실행 횟수를 한 줄에 출력한다.

피보나치 수열은 dp로 풀어야된다. 이 문제에서는 코드를 다 알려주고 횟수만 따로 추가해서 출력하면 되는 문제다.

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);
    }
}

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

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