백준 2193: 이친수

이친 수 문제 1이 연속으로 나오지 않는 이진수를 말한다. 풀이는 상당히 쉽게 떠오르는데 다이나믹 프로그래밍을 사용하면 된다. 나는 강의를 듣고 있는지라 바로 다이나믹인 걸 알고 있으나.. 그렇지 않아도 충분히 떠오를만 하다. 일단 이친수의 자리 수를 n이라고 하면 끝이 0으로 끝나면 d[n]0]에 1로 끝나면 d[n][1]에 저장하면 d[n][i] += d[n -1][k] (k는 0일 때는 i가 0, 1 둘 다 더해주고 1일 때는 0 부분에만 더해주면 되겠다.) 같은 점화식으로 표현할 수 있다.

#include <iostream>
using namespace std;
int input = 0;
long long d[100][2];
int main()
{
    cin >> input;
    d[1][0] = 0;
    d[1][1] = 1;
    for(int i = 2;i <= input; ++i)
    {
        d[i][1] += d[i - 1][0];
        d[i][0] += d[i - 1][1];
        d[i][0] += d[i - 1][0];
    }
    long long ans = d[input][0] + d[input][1];
    cout << ans;
}