[2193] 이친수

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

2193번: 이친수

 

접근:

• 1만 연속으로 못 붙이는 것을 감안하여, 재귀함수를 int getNum(int i, int last) 라고 만들었다. 여기서 last는 마지막에 붙는 수이다.
• 마지막 수가 1인 경우와 0인 경우를 나누어서 함수를 호출하면 된다.
• 첫 함수 호출 시, 1로 시작하는 것을 신경쓴다.

 

코드:

#include <iostream>
#include <memory.h>

using namespace std;

typedef long long dl;
int N;
dl cache[91][2];
// i부터 N까지의 이친수를 만들고 그 개수를 반환함
dl getPnum(int i, int last)
{
	if (i == N) return 1;

	dl& ret = cache[i][last];
	if (ret != -1) return ret;

	if (last == 1) return ret = getPnum(i + 1, 0);
	return ret = getPnum(i + 1, 1) + getPnum(i + 1, 0); // 1로 이어나가거나, 0으로 이어나가거나
}

int main()
{
	ios::sync_with_stdio(false);
	memset(cache, -1, sizeof(cache));
	cin >> N;
	// 첫번째 수는 반드시 1로 시작한다
	cout << getPnum(1, 1) << "\n";
	return 0;
}