[백준] 2193번 이친수

문제

https://www.acmicpc.net/problem/2193

풀이과정

쉬운 계단 수, 오르막 수를 풀어보고 나니 쉽게 풀 수 있었다.
먼저, D[1][0] 은 이친수의 조건 1규칙을 위반하기 때문에 0개였으며 D[1][1] 은 그냥 한개이다. 그 이후로 계속 생각해 본 결과 D[i][0]은 길이가 i-1인 수의 마지막 숫자가 0과 1일 경우의 이친수 개수를 더하면 됐다.
하지만 D[i][1] 의 경우는 이친수의 조건 2번을 적용하면 길이가 i-1이고 마지막 숫자가 0인 경우의 이친수의 개수와 같다는 사실을 알 수 있다. 이러한 결과를 식으로 나타내면 아래와 같다.

D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]

소스코드

#include <iostream>

using namespace std;

int N;
long long D[91][2], ans;

int main()
{
    cin.sync_with_stdio(false);

    cin >> N;

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

    for (int i = 2; i <= N; i++)
    {
        D[i][0] = D[i - 1][0] + D[i - 1][1];
        D[i][1] = D[i - 1][0];
    }

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

    cout << ans << "\n";

    return 0;
}