[BOJ 2193] 이친수

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

2193번: 이친수

---

이 문제는 의외로 단순하게 풀 수 있다.

 

길이가 N인 이친수의 개수를 구하는 것은 길이가 N - 1인 이친수에서 0으로 끝나는 이친수와 1로 끝나는 이친수를 찾아서 계산하면 된다.

 

이친수는 0으로 시작하지 않기 때문에 길이가 1인 이친수는 1개이다.

 

이친수는 11인 부분이 존재하지 않는다.

 

즉, N - 1인 이친수에서 1로 끝나는 이친수에는 0을 붙이고,

 

0으로 끝나는 이친수에는 0, 1을 둘 다 붙여서 생긴 이친수의 개수가 정답이 된다.

 

길이가 N인 이친수에서 0으로 끝나는 것의 개수 + 1로 끝나는 것의 개수 = 길이가 N인 이친수의 개수이다.

 

길이가 1 ~ N까지 순차적으로 0과 1로 끝나는 것의 개수를 구하면 된다.

 

예를 들어 

N = 1, 1

N = 2, 10

N = 3, 101 100

N = 4, 1010 1001 1000

N = 5, 10101 10100 10010 10001 10000

.....

 

위 예제를 보면

 

N의 0의 개수 = (N - 1)의 1의 개수 + (N - 1)의 0의 개수

N의 1의 개수 = (N - 1)의 0의 개수

 

이다!

---

#include <stdio.h>


unsigned long long int dp[91][2];
int main()
{

	int N;

	scanf("%d", &N);
	dp[1][1] = 1;
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] += dp[i - 1][0];
	}
	printf("%lld", dp[N][0] + dp[N][1]);
	return 0;
}