이친수_2193

2193

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

이친수: 이진수중 다음의 두 조건을 만족하는 수.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

그러므로 점화식을 세울 때 우리는 끝의 문자에 따라 d[n][1], d[n][0]으로 나누어 생각하여야 한다.

 

이친수는 0으로 시작하지 않으므로 초기값은 d[1][1] = 1, d[1][0] = 0 이다.

 

그렇다면 이 초기값을 기준으로, 나머지 점화식을 세울 수 있다. 여기서는 두번째 조건에 집중하면 된다.

 1은 연속해서 사용할 수 없기 때문에 두번째 조건에 집중하면 점화식은 d[n][1] = d[n-1][0], d[n][0] = d[n-1][0] + d[n-1][1] 이다.

 

//2193 이친수

#include <stdio.h>
long long d[91][1];
int main(void)
{
    int a;
    scanf("%d", &a);

    d[1][1] = 1;
    d[1][0] = 0;

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

    printf("%lld", d[a][1] + d[a][0]);
}