[백준] - 피보나치 함수 - 복습

[https://www.acmicpc.net/problem/1003]

계산해야 되는 피보나치 수 N은 40보다 작은 수
각 피보나치 수 마다의 1과 0사용의 갯수는 이전 수를 계산할때 호출 수의 합
f(3) = f(2) + f(1)

f(2) = 1한번 0한번 호출
f(1) = 1한번 호출
f(3) = 1두번 0한번 호출

Dynamic Programing
큰 문제를 작은 문제로 분할해서 생각하며 작은 문제들의 결과를 저장해두었다가 재사용

#include <iostream>

using namespace std;

int cnt0;
int cnt1;
int DP[50][2];

int main()
{
    int T;
    cin >> T;

    DP[0][0] = 1;
    DP[0][1] = 0;
    DP[1][0] = 0;
    DP[1][1] = 1;

    for (int i = 2; i <= 40; i++)
    {
        DP[i][0] = DP[i - 1][0] + DP[i - 2][0];
        DP[i][1] = DP[i - 1][1] + DP[i - 2][1];
    }

    for (int i = 0; i < T; i++)
    {
        int N;
        cin >> N;

        cout << DP[N][0] << " " << DP[N][1] << endl;

    }

}