백준 1003번) 피보나치 함수

본문의 코드보다 더 효율적인 코드가 분명 존재합니다.

참고만 해주시면 감사하겠습니다.

코드 지적은 언제나 환영입니다.

---

풀이

우선, 피보나치 수는

f(2) = f(1) + f(0) = 1

f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = 2

f(4) = f(3) + f(2) = f(2) + f(1) + f(1) + f(0) = f(1) + f(0) + f(1) + f(1) + f(0) = 3

f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(2) + f(1) + f(1) + f(0)+ f(1) + f(0) + f(1) = f(1) + f(0) + f(1) + f(1) + f(1) + f(0) + f(1) + f(0) = 5

...

과 같이 계산할 수 있다.

 

문제에서 주어진 피보나치 함수를 이용했을 시간초과가 발생한다.

시간초과를 방지하기 위해 재귀함수가 아닌 while문을 이용하여 피보나치 수를 계산하였다.

0일 때는 피보나치 수가 0이기 때문에 "1 0"을 출력하고

1일 때는 피보나치 수가 1이기  때문에 "0 1"을 출력했다.

2이상일 때는 while문을 이용하여 피보나치 수를 계산한다.

 

3
1 2
결과: 2
4
2 3
결과: 3
5
3 5
결과: 5
6
5 8
결과: 8

본문의 코드에

cout << "결과: " << c << '\n';

를 추가하여 결과 값을 확인해 보았을 때 일정한 규칙을 찾을 수 있다.

ex) fibonacci(6)에서 0의 갯수는 fibonacci(5)의 결과 값 이고 1의 갯수는 fibonacci(6)의 결과 값이다.

 

코드

#include "iostream"

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc;
    cin >> tc;

    for(int i = 0 ; i < tc ; i++){
        int n;
        cin >> n;

        int a = 0, b = 0, c = 0;

        if(n==0){
            cout << "1 0\n";
            continue;
        }
        else if(n==1){
            cout << "0 1\n";
            continue;
        }
        else if(n>1){
            a = 0;
            b = 1;
            int count = 2;
            while (count <= n)
            {
                c = a + b;
                a = b;
                b = c;
                count += 1;
            }
        }
        cout << a << " " << b << '\n';
    }

    return 0;
}