[ 백준 9625 ] BABBA (C++)

백준의 BABBA(9625) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

버튼을 한번 누르게 되면 'A'는 'B'로, 'B'는 'AB'로 변하게 된다.

A와 B가 변하는 규칙이 다르니, 이 2개를 각각의 수식으로 만들어서 표현해보자.

FA[K] = C 라는 수식과 FB[K] = C 라는 수식을 사용해보자.

FA[K] = C의 의미는 "버튼을 K번 눌렀을 때, 화면에 있는 'A'의 갯수는 C개입니다." 를 의미하고

FB[K] = C의 의미는 "버튼을 K번 눌렀을 때, 화면에 있는 'B'의 갯수는 C개입니다." 를 의미한다.

가장 처음에는, 화면에 'A'만 표시되어 있으므로 이를 수식으로 표현해보면

FA[0] = 1

FB[0] = 0 이 될 것이다.

버튼을 한번 누르게 되면

FA[1] = 0

FB[1] = 1 이 될 것이다.

왜냐하면, 처음에 화면에 있던 'A'가 버튼을 한번 누름으로써 'B'가 되어버리기 때문에 버튼을 한번만 누른다면,

화면의 상태는 'B'가 될 것이다.

즉, K번 눌렀을 때의 'A'의 갯수는 이전 화면에 있었던 'B'의 갯수가 된다.

위의 2가지 상황에서도 알 수 있듯이, FA[1] = FB[0] 이 된다.

반대로, K번 눌렀을 때의 'B'의 갯수는 이전 화면에 있었던 'A'의 갯수 + 'B'의 갯수가 된다.

왜냐하면, 이전 화면에 있었던 'A'가 모두 'B'로 바뀔 것이고, 'B'가 'BA'로 바뀔 것이기 때문이다.

이를 정리해보면

FA[K] = FB[K - 1]

FB[K] = FB[K - 1] + FA[K - 1] 이 된다.

이를 점화식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N;
int A_Cnt[MAX];
int B_Cnt[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    A_Cnt[0] = 1;
    B_Cnt[0] = 0;
    A_Cnt[1] = 0;
    B_Cnt[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        A_Cnt[i] = B_Cnt[i - 1];
        B_Cnt[i] = B_Cnt[i - 1] + A_Cnt[i - 1];
    }
    cout << A_Cnt[N] << " " << B_Cnt[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}