BOJ 2193 이친수

boj 2193 이친수

쉬운 계단 수, 오르막 수와 비슷한 류의 문제이다. 길이가 N인 이친수의 경우의 수를 끝이 0이거나 1인 경우로 나눈다. 초기 값으로는 길이가 1일 때와 2일 때를 잡고, 그 값을 쌓아올려 길이가 N일 이친수의 갯수를 구한다. 길이가 3 이상인 이친수의 경우, 끝이 0인 경우 그 앞의 수로 0, 1이 올 수 있다. 끝이 1인 경우는 그 앞의 수로 0만 올 수 있다. 이를 바탕으로 테이블 D[i][j]를 길이가 i이고 맨 끝 수가 j인 이친수의 갯수로 정의하고 점화식을 설정했다.

j가 0일 때, D[i][j] = D[i-1][j] + D[i-1][j+1]
j가 1일 때, D[i][j] = D[i-1][j-1]

점화식을 바탕으로 코드를 구현했다.

#include <iostream>
using namespace std;

int n;
long long ans;
long long D[95][5];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    D[1][1] = 1;
    D[2][0] = 1;

    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j <= 1; j++)
        {
            if (j == 1) D[i][j] = D[i - 1][j - 1];
            else D[i][j] = D[i - 1][j] + D[i - 1][j + 1];
        }
    }

    ans = D[n][0] + D[n][1];

    cout << ans;
}