[ 백준 1003 ] 피보나치 함수 (C++)

백준의 피보나치함수(1003) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 피보나치 수열이라는 것은 배열 N의 값이 N-1 + N-2 로 이루어진 수열이다.

- 피보나치 수열은 원래 재귀로 짜는 것이 일반적이다. 문제에서 주어졌듯이, 재귀 호출을 통한 구현이 일반적이다.

- 하지만 피보나치 수열에서 너무 큰 N값의 피보나치 값을 구하기 위해서는, 그 큰 값 만큼의 재귀 호출을 실행해야 하고

   그 만큼 스택에 메모리가 쌓이게 되고 자연스럽게 실행시간이 오래 걸리게 된다.

- 이 문제에서는 피보나치 수열을 Dynamic Programming으로 구현해보는 것이다. 

- 구현하면서 나오는 0의 갯수와 1의 갯수를 출력시키면 된다.

[ 문제풀이 ]

1) 동적 계획법으로 문제를 해결하기 위해서 먼저 가장 작은 식을 구한다.

    1-1) 나는 이 문제에서 2차원 배열을 사용했는데, 그 이유는 특정 N값 호출 시 Count된 0의 갯수와 1의 갯수를 

          저장해 놓기 위함이다. 

          DP[a][0] = a를 호출 했을 때, 0의 갯수 / DP[b][1] = b를 호출 했을 때, 1의 갯수

2) 가장 작은 식을 통해 도출해 낼 수 있는 점화식을 구한다.

   2-1) 피보나치 수열에서 점화식은 DP[i][0] = DP[i - 1][0] + DP[i - 2][0]

                                        DP[i][1] = DP[i - 1][1] + DP[i - 2][1] 로 주어지게 된다.

          

   2-2) 가장 작은 값인 DP[0][0] 와 DP[1][1] 은 1의 값 , DP[0][1] 과 DP[1][0]는 0의 값을 갖게 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 41
using namespace std;
 
int N, Zero_Cnt, One_Cnt;
int DP[MAX][2];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
    Zero_Cnt = 0;
    One_Cnt = 0;
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[0][1] = DP[1][0] = 0;    
    DP[0][0] = DP[1][1] = 1;    // 0을 호출 시 0의 갯수 & 1을 호출 시 1의 갯수 = 1
 
    for (int i = 2; i <= N; i++)
    {
        DP[i][0] = DP[i - 1][0] + DP[i - 2][0];
        DP[i][1] = DP[i - 1][1] + DP[i - 2][1];
    }
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << DP[N][0] << " " << DP[N][1] << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}