(c++)백준 2133번: 타일 채우기

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

2133번: 타일 채우기

☆가로 길이가 2 늘어날 때마다 케이스가 2개씩 더 늘어난다.

 

 

 

 

※점화식※

dp[0] = 1 (추가 케이스 더할 때 필요)

dp[1] = 0

dp[2] = 3

dp[x] = 3 * dp[x-2] + 2 * dp[x-4] + ··· + 2 * dp[0] (마지막 항은 추가케이스 2개 더하는 항)

 

#include <iostream>
using namespace std;

int N;
long long dp[31];

void DP() {
	dp[0] = 1;//추가 케이스 더할 때 필요
	dp[1] = 0;
	dp[2] = 3;
	//N이 짝수일 때만 타일을 채울 수 있음
	for (int i = 4; i <= N; i += 2) {
		for (int j = 2; j <= i; j += 2) {
			int Mul = j == 2 ? 3 : 2;//추가 케이스 개수
			dp[i] += Mul * dp[i - j];
		}
	}
	cout << dp[N] << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}