[210527][백준/BOJ] 2193번 이친수

문제

입출력

풀이

이친수는 0으로 시작하지 않으며 1이 두 번 연속 나타나지 않은 수를 말한다.
즉 첫번째는 무조건 1이 나와야 하고 1이 연속 두번해서 나타날 수 없으므로 두번째는 0이 나와야한다.
따라서 이친수는 10으로 시작하는것을 알 수 있다.

이 성질을 이용해서 이친수를 찾아보면
n=1 1
n=2 10
n=3 100 101
n=4 1000 1001 1010
n=5 10000 10001 10010 10100 10101
...
다음과 같다.

여기서 공식을 찾아볼 수 있는데 n=5일때의 이친수 중에서 앞에 10을 제외하고 보면
000, 001, 010, 100, 101라는 숫자들을 찾을 수 있는데 이는 n=3과 n=4의 값들임을 알 수 있다.
(n=4에서 앞에 1을 제외하고 000, 001, 010과 n=3의 100, 101)

따라서 점화식은 다음과 같다.

d[n] = d[n-1] + d[n-2] 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

lli d[92];
lli dp(int n)
{
	d[1] = 1;
	d[2] = 1;

	for (int i = 3; i <= n; ++i)
		d[i] = d[i - 1] + d[i - 2];
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	cout << dp(n);
}