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

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

[ 문제 바로가기 ]

[ 문제풀이 ]
주어진 N 값에 대한 피보나치 함수 값을 구할 때, 그 과정에서 '0'과 '1'이 몇 번씩 출력되었는지 구해야 하는 문제이다.

피보나치 수열에 대해서 간략하게만 알아보자.

피보나치 수열은 A[n] = A[n - 1] + A[n - 2] 의 규칙을 갖는 수열이다.

즉, 1, 1, 2, 3, 5, 8, 13... 이런식으로 진행되는 수열을 의미한다.

본인은 이 문제를 Dynamic Programming 방법으로 접근해 보았다.

DP[50][2] 라는 2차원 int형 배열 하나를 통해서, 0과 1의 갯수를 관리해 주었다.

DP[a][0] = b 의 의미는 "피보나치 수열에서 a번째 피보나치 값을 구하는 과정에서 호출되는 0의 횟수는 b번입니다." 이다.

DP[a][1] = b 의 의미는 "피보나치 수열에서 a번째 피보나치 값을 구하는 과정에서 호출되는 1의 횟수는 b번입니다." 이다.

그럼 먼저, 초기값을 생각해보자.

DP[0][0] 의 값은 얼마일까 ?? 이를 해석해보면, "0번째 값을 구하는 과정에서 호출되는 0의 횟수는 몇 번입니까?" 로 말할 수

있다. 문제에서 "fibonacci(0)은 0을 출력하고, 0을 리턴한다." 라는 문구에서 알 수 있듯이, 호출되는 0의 횟수는 '1번' 이라는 것을 알 수 있다.

그렇다면, DP[0][1]의 값은 얼마일까 ? 한번 더 해석해보면, "0번째 값을 구하는 과정에서 호출되는 1의 횟수는 ?" 으로 말할

수 있다. 0을 호출하게 되면, 0을 출력하고 그대로 끝내버리기 때문에, 1은 나오지가 않는다. 즉 ! DP[0][1]의 값은 '0'이 된다.

그럼, DP[1][0]의 값은 얼마일까?? 1을 호출하게되면, 1을 그대로 return 하고 끝나버리기 때문에, 0은 호출되지 않는다.

따라서 DP[1][0] = 0이 된다. 반대로, DP[1][1]의 값은, 1을 한번 출력하기 때문에, DP[1][1]의 값은 1이 된다.

위의 내용을 통해서 초기식을 정리해보면...

DP[0][0] = 1

DP[0][1] = 0

DP[1][0] = 0

DP[1][1] = 1 이라는 것을 알 수 있다.

그럼, 이제부터는 위의 식을 토대로 더 큰 값들에 대해서 알아보자.

DP[2][0] 의 값을 생각해보자. "피보나치 수열에서 2번째 값을 구하는 과정에서 호출되는 0의 횟수는 몇 번일까요?" 라고

묻는 것과 같다.

피보나치 수열이 위에서도 말했듯이, N - 1, N - 2번째 값들의 합으로 N번째 값이 이루어진 수열이다.

마찬가지로 0의 횟수 또한 동일하다. N - 1, N - 2번째에서 사용된 0의 횟수들의 합이 곧, N번째 값을 호출했을 때, 0이 출력되는 횟수가 된다.

1도 동일하다. N - 1, N - 2번째에서 사용된 1의 횟수들의 합이 곧, N번째 값을 호출했을 때, 1이 출력되는 횟수가 된다.

즉 ! 점화식을 적어보자면 다음과 같이 적을 수가 있다.

DP[N][0] = DP[N - 1][0] + DP[N - 2][0]

DP[N][1] = DP[N - 1][1] + DP[N - 2][1]

위의 식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N;
int DP[MAX][2];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[0][0] = 1;
    DP[0][1] = 0;
    DP[1][1] = 1;
    DP[1][0] = 0;
    
    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;
}