[백준] 2193번 이친수

문제 링크

 

풀이

다섯 번째 항까지 직접 경우의 수를 세어 보면 피보나치 수열과 동일한 규칙을 찾을 수 있습니다. 90번째 항까지 구해야 하는데, int형은 표현 범위를 초과하기 때문에 점화식은 long long으로 만들어줍니다. 규칙을 이렇게도 생각해볼 수 있습니다. 다섯 자리라고 할 때 10xxx0인 경우와 10xx01인 경우입니다. 0으로 끝날 때 d[n-1]과 01으로 끝나는 경우인 d[n-2]를 더해서 d[n]을 구하는 것입니다. d[n] = d[n-1] + d[n-2]이고 초기값만 잘 세팅해주면 됩니다.

 

코드

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