백준 / 1003번 / 피보나치 함수 / C++

# 출처 : https://www.acmicpc.net/problem/1003

처음에 단순하게 count 변수 두개를 선언해서 0과 1을 호출하는 횟수를 셌는데 시간초과가 났다.

따라서 i번째 수의 0과 1의 호출 횟수는 i-1번째의 0과 1, i-2번째의 0과 1 각각의 횟수의 합과 같은 규칙을 찾아

처음부터 배열에 담아두는 형식으로 풀었다.

# 풀이

#include <iostream>
 
using namespace std;
 
int T, N;
int DP[42][2];
 
int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
 
    DP[0][0] = 1; DP[0][1] = 0;
    DP[1][0] = 0; DP[1][1] = 1;
    for (int i = 2; i < 42; ++i)
    {
        DP[i][0] = DP[i - 1][0] + DP[i - 2][0];
        DP[i][1] = DP[i - 1][1] + DP[i - 2][1];
    }
 
    cin >> T;
    for (int i = 0; i < T; ++i)
    {
        cin >> N;
        cout << DP[N][0] << " " << DP[N][1] << '\n';
    }
    return 0;
}