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

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

2193번: 이친수

index(0~n-1) 번이 number(0 또는 1)일 때 이친수의 개수를 구하는 함수를 만든다. 이 함수의 number가 0이면 그다음 숫자가 0일 때와 1일 때를 고려하지만, number가 1이면 그다음 숫자가 0일 때만 고려한다(이친수에서 1이 두 번 연속 나오지 않는다는 성질 이용), 그리고 0번 index의 number는 무조건 1이어야 한다(이친수는 0으로 시작할 수 없다는 성질 이용)

 

코드

#include <iostream>
#include <utility>
using namespace std;

int n;
long long cache[90][2];

void makeCache()
{
	//-1로 초기화한다
	for (int i = 0; i < 90; i++)
		for (int j = 0; j < 2; j++)
			cache[i][j] = -1;
}

//index(0~n-1)번이 number(0또는1)일때 이친수의 개수
long long solve(int index, int number)
{
	//이친수의 끝일때
	if (index == n-1)
		return 1;

	long long& ret = cache[index][number];

	//이미 계산한적이 있을때
	if (ret != -1)
		return ret;

	//number가 0이면 그 다음 숫자는 0또는1이 올 수 있다
	if (number == 0)
		ret = solve(index + 1, 0) + solve(index + 1, 1);

	//number가 1이면 그 다음 숫자는 무조건 0이어야한다.
	else if (number == 1)
		ret = solve(index + 1, 0);

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cache 초기화
	makeCache();

	cin >> n;

	//0번 index는 0으로 시작할수 없으므로 무조건 1이어야한다
	cout << solve(0, 1);

	return 0;
}