[백준] 알고리즘 2133번 - 타일 채우기 문제

#include <bits/stdc++.h>
using namespace std;
int dp[31];

int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[0]=1, dp[2] = 3;
	for (int i = 4; i <= n; i += 2) {
		dp[i] = dp[i - 2] * 3;
		for (int j = 4; j <= i; j += 2) {
			dp[i] += dp[i - j] * 2;
		}
	}
	cout << dp[n];
	return 0;
}

3x2 인경우는 총 3가지의 경우로 도형을 만들 수 있다.

홀수번인 경우에는 타일을 완벽하게 깔 수 없으므로 생각하지 않는다.

이제 dp[i] 에는 3xi 번째에 타일을 깔 수 있는 경우의 수를 저장한다.

3x4 인경우를 생각해보자

단순히 3x2의 경우에 3을 곱한다고 생각하면 안된다.

이 경우의 수 + 새로 생기는 타일 2개를 더해줘야 한다.

3x6인 경우를 생각해보자.

3x4의 경우의 수 + dp[4]의 새로생기는 타일 x dp[2]의 경우의 수 + 새로 생기는 타일 2개를 더한다.