boj 1003 피보나치 함수 c++

boj 1003 피보나치 함수 c++

 

 

들어오는 숫자 N은 0~50까지의 범위이다.

이에 대해 피보나치 함수에서 0과 1을 몇 번 출력하는지를 묻는 문제인데,

사실 2부터 50까지의 범위에서 어떤 수가 fibo(0), fibo(1)을 몇 번 호출하는지는 n-1번째에서 나온 fibo(0)과 fibo(1)의 갯수에 n-2번째에서 나온 fibo(0)과 fibo(1)의 갯수를 더한 것 과 같다.

그런데 우리는 시간이 무려 0.25초 밖에 주어지지 않아 아주 촉박하기도 한데다

기존의 피보나치 함수를 호출하면서 카운트 하기에는 n이 50이 들어오거나 했을 때 그냥 영원히 컴퓨터를 돌리고 있어야 할 것이다.

 

따라서 이것을 미리 배열에 담아두기로 한다.

fibo(0)과 fibo(1)을 미리 배열에 넣어놓고, 2~50까지는 위에서 설명한 원리대로 집어넣는다.

 

코드

# include <bits/stdc++.h>
using namespace std;

# define X first
# define Y second

pair<int, int> arr[51];
int testcaseCount;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    arr[0].X = 1;
    arr[0].Y = 0;
    arr[1].X = 0;
    arr[1].Y = 1;
    for (int i = 2; i < 51; i++)
    {
        arr[i].X = arr[i - 1].X + arr[i - 2].X;
        arr[i].Y = arr[i - 1].Y + arr[i - 2].Y;
    }
    
    cin >> testcaseCount;
    while (testcaseCount--)
    {
        int t;
        cin >> t;
        cout << arr[t].X << ' ' << arr[t].Y;
        if (testcaseCount != 0)
            cout << "\n"; // 마지막 출력에 개행이 들어가니 실패하더라..
    }
    return (0);
}

 

 

백준 1003 피보나치 함수 cpp