Baekjoon 2133

타일 채우기

#include <iostream>

using namespace std;

int N;

int dp[31];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

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

	for (int i = 4; i <= N; i = i + 2)
	{
		dp[i] = 3 * dp[i - 2]; // 2개 빼고 일반 적용
		// =    ㅣㅣ    ㅡ
		// ㅡ or ㅡ or ㅣㅣ 

		for (int j = i - 4; j >= 0; j = j - 2)
		{
			dp[i] = dp[i] + 2 * dp[j];
		}
		// 4 + 2n개씩 빼며 특이한 문양 적용
		// ㅣ==ㅣ     ㅡㅡ    ㅣ===ㅣ
		//  ㅡㅡ  or ㅣ==ㅣ or ㅡㅡㅡ
	}

	cout << dp[N] << "\n";

	return 0;
}