[BOJ 2193] 이친수

문제 출저 : https://www.acmicpc.net/problem/2193

 

풀이 :

 

DP문제입니다.

이친수는

 

1) 첫번째 숫자는 0으로 시작할수 없다.

2) 1이 연속으로 나올 수 없다.

 

이 두가지 조건을 만족해야합니다.

따라서 데이터를 쌓을 때 2번 조건을 통해 얻어 낼 수 있는 아래의 규칙에 따라 쌓으시면 됩니다.

 

규칙 1) 현재 자릿수의 끝 수가 1인 이친수(cache[i][1])는

          이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])에서 밖에 만들 수 없다.

규칙 2) 현재 자릿수의 끝 수가 0인 이친수(cache[i][0])은

          이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])와 1인 이친수(cache[i - 1][1]) 둘 다에서 만들 수 있다.

 

#include<stdio.h>
 
int n;
long long int cache[90][2];
 
int main()
{
    scanf("%d", &n);
    cache[0][1] = cache[1][0] = 1;
    for (int i = 2; i < n; i++)
    {
        cache[i][1] = cache[i - 1][0];
        cache[i][0] = cache[i][1] + cache[i - 1][1];
    }
    printf("%lld", cache[n - 1][0] + cache[n - 1][1]);
}