[BOJ] 1003_피보나치 함수

피보나치 함수

문제링크: https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

단순 피보나치 함수 문제인 줄 알았다.
1의 개수와 0의 개수를 파악해서 출력해야한다.
하지만 주어진 메소드에서

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

결국 피보나치 값은 1의 개수임을 알 수 있다.
그렇다면 0의 개수는 무엇일까?
재귀함수의 total 횟수에서 fibonacci(n)을 뺀 값이 0의 개수가 될 것이다.

그럼 total은 어떻게 구하는가?
주어진 예제 코드를 토대로 피보나치 수와 total 를 출력하여 1부터 20까지 비교를 해보았다.

출력

20
1
1 : 1
2
1 : 2
3
2 : 3
4
3 : 5
5
5 : 8
6
8 : 13
7
13 : 21
8
21 : 34
9
34 : 55
10
55 : 89
11
89 : 144
12
144 : 233
13
233 : 377
14
377 : 610
...

규칙은 fibonacci(n)의 total 재귀 함수 횟수는 fibonacci(n+1)과 같음을 알 수 있다.
따라서, 0의 횟수는 total - fibonacci(n)이다.

피보나치 수열을 for문을 통해 O(n)으로 할 수도 있으나 시간 단축을 위해 피보나치의 일반항 공식을 이용하였다.

정답코드

#include<iostream>
#include<math.h>
using namespace std;

double fibo(int n) {
    double sqrt5 = sqrt(5);

    double A = (1 + sqrt5) / 2;
    double B = (1 -  sqrt5) / 2;

    double temp = (pow(A,n) - pow(B,n)) / sqrt5;
    return  temp;
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;

        int total = fibo(a + 1);
        int oneCount = fibo(a);
        int zeroCount = total - oneCount;

        cout << zeroCount << " " << oneCount << endl;
    }
    return 0;
}