백준 1003번 : 피보나치 함수 [C++]

주소 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

typedef struct
{
    int number;
    int one;
    int zero;
}Num;

void fibonacci(int n) 
{
    Num N[41];
    if (n == 0)
    {
        cout << 1 << ' ' << 0<<'\n';
    }
    if (n == 1)
    {
        cout << 0 << ' ' << 1<<'\n';
    }

    if (n > 1)
    {
        N[0].number = 0;
        N[0].one = 0;
        N[0].zero=1;
        N[1].number = 1;
        N[1].zero = 0;
        N[1].one=1;
        for (int i = 2;i <= n;i++)
        {
            N[i].number = N[i - 2].number + N[i - 1].number;
            N[i].one = N[i - 2].one + N[i - 1].one;
            N[i].zero = N[i - 2].zero + N[i - 1].zero;
        }
        cout << N[n].zero << ' ' << N[n].one << '\n';
    }
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T, N;
    cin >> T;
    while (T != 0)
    {
        cin >> N;
        fibonacci(N);
        T--;
    }
}

마무리 : 피보나치 함수는 문제에 나와 있는 예제로 풀 수 있지만 그러면 시간이 초과하기 때문에 다른 방식으로 구해야한다. 그 방식은 다이나믹 프로그래밍인 것이다. 

다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘이다. 나는 이 방법을 사용하여 풀었긴 했지만 0과 1이 출력되는 횟수를 세어주면 되지만 피보나치 수까지 구한 코드를 짜버렸다.