[BOJ/C++] 2133 타일 채우기

문제

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

풀이

N=1 ANS : 0
N=2 ANS : 3
N=3 ANS : 0
N=4 ANS : 11
N=5 ANS : 0
N=6 ANS : 41
N=7 ANS : 0
N=8 ANS : 153

규칙 찾아서 살짝 야매로 풀었는데 정석적인 점화식 도출 방법은 아래와 같다.

코드

#include <iostream>
#include <vector>

using namespace std;

int dp[31];

int main() {
	int n;

	cin >> n;
	dp[0] = 1;
	dp[1] = 0;
	dp[2] = 3;
	for (int i = 4; i <= n; i++) {
		if (i % 2 == 0) {
			dp[i] = dp[i - 2] * 4 - dp[i - 4];
		}
	}

	cout << dp[n];
	
	return 0;
}