백준 1003번 피보나치 함수 [C언어]

Sol)

#include <stdio.h>

int main()
{
    int count_zero[41] = {1, 0}; //0 ~ n번째 피보나치 수가 호출하는 0의 수를 저장할 배열.
    int count_one[41] = {0, 1}; //0 ~ n번째 피보나치 수가 호출하는 1의 수를 저장할 배열.
    int n = 0; //input.
    int tc = 0; //test case.

    scanf("%d", &tc);

    while(tc--) {
        scanf("%d", &n);

        for (int i = 2; i <= n; i++) {
            count_one[i] = count_one[i - 1] + count_one[i - 2];
            count_zero[i] = count_zero[i - 1] + count_zero[i - 2];
        }

        printf("%d %d\n", count_zero[n], count_one[n]);
    }

    return 0;
}

 

• 풀이 방향

시간 제한이 0.25초밖에 되지 않기 때문에 n이 40으로 그렇게 크지 않더라도 재귀 깊이가 매우 깊어져 재귀함수로는 풀 수 없다. 그렇다면 이 문제또한 지난 두 포스트의 문제들처럼 배열 or 포인터를 이용해야 풀어야겠다. 피보나치 수열이란 결국 Fn = Fn-1 + Fn-2 이라는 점화식을 만족시키는 수들의 집합이다. 그리고 우리는 지금까지 n번째 수를 알기 위해 가장 간단한 0번째 수와 1번째 수부터 더해나가는 방법을 채택했다. 또한, 문제에서 주어진 재귀함수와 우리가 지난 두 피보나치 수 문제에서 짠 for문을 보면 피보나치 수란 결국 0과 1의 합으로 이루어져 있다는 걸 알 수 있다. 따라서 n-1번째 수와 n-2번째 수가 호출한 0과 1의 개수를 합치면 n번째 수가 호출한 0과 1의 수를 알 수 있게된다.

 

• 풀이

0번째 피보나치 수는 0, 1번째 피보나치 수는 1이다. 각각이 호출한 0과 1의 개수는 각각 1 0, 0 1이 된다. 이들을 각각 i번째 피보나치 수가 호출한 0의 횟수와 1의 횟수를 저장할 배열 count_zero와 count_one에 저장해 준다. while문으로 테스트 케이스의 크기만큼 n번째 수가 호출한 0의 개수와 1의 개수를 구한다. 구하는 방법은 위에서 설명했던 것처럼 0과 1번째 피보나치 수부터 시작해서 n-2와 n-1번째 피보나치 수가 호출한 0과 1의 개수를 더해 구한다. 

**참고로 while문의 parameter를 --tc로 하게되면 tc번 반복하지 않고 tc - 1번만큼 반복하게 되므로 주의하자. 이는 후위 증감 연산자와 전위 증감 연산자의 작동 방식의 차이때문에 그렇다. 

 

• 문제에 대한 사견

재귀 함수를 배울 때 재귀함수는 효율이 나쁠 수 있다는 말을 들었었다. 재귀 호출하는 깊이가 깊어질수록 함수를 호출하는 횟수가 너무 많아지기 때문이다. 이 문제는 재귀함수의 이런 문제를 직접 숫자로 알아볼 수 있는 문제였던 것 같다. n이 40만 돼도 0을 63245986번, 1을 102334155번 호출한다는 결과를 얻을 수 있기 때문이다.