[ 백준 2193 ] 이친수 (C++)

백준의 이친수(2193) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 이친수 라는 것은 이진수 중에서도, 0으로 시작하지 않으면서, 1이 두번 연속으로 나오지 않는 숫자들을 의미한다.

- 정수를 입력으로 받고, 그 정수자리 이친수의 갯수를 구하는 것이 문제이다.

[ 문제풀이 ]

1) 먼저 나는 DP배열을 하나 사용했다. DP[a] = " a자릿 수 이친수의 갯수 " 를 의미한다.

2) 1)에서 말한 의미를 토대로 초기식을 세워보면 DP[0] = 0 , DP[1] = 1 , DP[2] = 1이 될 것이다.

3) 2)의  내용을 좀 더 자세히 말해보자면

   "자릿수가 0인 이친수의 갯수 = 0"

   "한 자릿수의 이친수 = 1" (1개) , 두 자릿수의 이친수 = 10 (1개)" 가 된다.

   그럼 세 자릿수 이친수 = ?? 계산해보면 '100, 101' 2개가 된다.

   문제에서 제시한 조건을 만족시키기 위해서는 제일 앞에 2숫자가 10 으로 고정되어야 한다는 것을 알 수 있다.

   그럼 4자릿 수 이친수를 생각해보자. 앞에 2자리는 무조건 10으로 고정되어야 하므로

   1000, 1001, 1010 이렇게 3개가 나오게 된다. 그럼 앞에 2자리를 빼고, 뒤에 두 자리만 보게되면 '00, 01, 10' 을 확인할 

   수 있다. 저 3개의 숫자는 두자릿수의 이친수의 제일 마지막 뒤에 2개 + 세자릿수 이친수들의 제일 마지막 2개와 같다.

4) 3)에서 말한 내용을 토대로, 5자릿도 생각해보게 되면, 아마 결과는 세자릿수 이친수들의 제일 마지막 3개 +, 네자릿수 

   이친수들의 제일 마지막 3개" 총 5개가 나오게 된다. (생각해보면 금방 나온다..)

5) 이를 토대로, 점화식을 만들어 보자면 

   DP[N] = DP[N-1] + DP[N-2]가 된다. 

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
typedef long long ll;
using namespace std;
 
ll N;
ll DP[91];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    //1000 1001 1010 
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 1;
    for (int i = 3; i <= N; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }
}
 
void Solve()
{
    Input();
    Solution();
    cout << DP[N] << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}