Level 23 - 3번

1)함수로 빼서 생각하는거!
2)연속되지만 않으면 된다.

[아이디어]
1)path의 자릿수가 3보다 작으면 패스
2)현재값이랑, 그전값이랑 다르면 패스
3)그전값이랑, 그전전값이랑 다르면 패스

#include <iostream>
#include <string>

using namespace std;

int n;
char path[10];
int cnt = 0;
int isPossible(int lev) {
	if (lev < 3)return 1;
	if (path[lev - 1] != path[lev - 2])return 1;
	if (path[lev - 2] != path[lev - 3])return 1;
	return 0;
}
void run(int lev) {
	if (isPossible(lev) == 0)return;
	if (lev == n) {
		cnt++;
		return;
	}
	for (int i = 0; i < 3; i++) {
		path[lev] = 'A' + i;
		run(lev + 1);
		path[lev] = 0;
	}
}
int main() {

	cin >> n;
	run(0);
	cout << cnt << "\n";


	return 0;
}