[백준][DP] 이친수

1. 문제 주소

 

2193번: 이친수

2. 문제

n자릿수의 이진수가 있을 때 1이 연속하여 존재하지 않는 경우의 수를 구하는 문제이다. 2차원 배열을 이용하여 마지막 자릿수의 숫자가 0, 1 두 가지 경우로 나누어서 나올 수 있는 경우의 수를 구하였다. 마지막 자릿수가 0인 경우 그다음에 0과 1이 올 수 있지만 1인 경우에는 0밖에 오지 못한다. 이를 이용하여 코드를 작성하였다.

3. 소스 코드

#include <iostream>
using namespace std;
long long d[91][2];
 
int main(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 1; j++)
        {
            if (i == 1)
                d[i][1] = 1;
            else
            {
                if (j == 0)
                    d[i][j] += d[i - 1][1] + d[i - 1][0];
                else
                    d[i][j] += d[i - 1][0];
            }
            
        }
    }
 
    cout << d[n][0] + d[n][1] << '\n';
    return 0;
}