24416: 알고리즘 수 - 피보나치 수 1

어떤 문제인가?

#코드 1, #코드 2 부분의 실행 횟수를 구하여라.

fib(n) {
    // if (n = 1 or n = 2)
    then return 1; # 코드 1
    // else return (fib(n - 1) + fib(n - 2));
}

fibonacci(n) {
    // f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    // return f[n];
}

시행착오 횟수

한 번에 해결.

1차 시도: AC

#include <stdio.h>
#define MAX(a, b) a > b ? a : b

int cnt[41];

int main() {
    int N;
    scanf("%d",&N);
    cnt[1] = cnt[2] = 1;
    for(int i=3;i<=N;i++)
        cnt[i] = cnt[i-1] + cnt[i-2];
    printf("%d %d", cnt[N], MAX(0, N-2));
}

풀고 나서 보니까 $N>5$여서 MAX(a,b) 함수가 필요 없었다.

다른 분들의 풀이

풀이 원리는 동일하므로 생략한다.