타일 채우기

#include <stdio.h>

int p[100001];
int a[100001];

int get_max(int a, int b) {
	return a > b ? a : b;
}
int get_min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	//freopen("input.txt", "rt", stdin);
	int n;
	scanf("%d", &n);

	p[0] = 1;
	p[2] = 3;

	if (n % 2 != 0) {
		printf("0");
		return 0;
	}
	for (int i = 4; i <= n; i = i + 2) {
		for (int j = 0; j <= i - 4; j++) {
			p[i] += 2 * p[j];
		}
		p[i] += 3 * p[i - 2];
	}
	printf("%d", p[n]);
	return 0;
}