Boj 2718) 타일 채우기

문제

백준 2718

설명

타일 채우기 2XN, 3xN 을 제대로 이해했으면 쉽게 풀리는 문제.

4Xt 크기의 타일이 있을 때

• 더이상 세로로 쪼갤 수 없는 경우의 수 를 \(Unit(t)\) 라고 하면
• \(Ans(n) = \sum_{i=1}^{i=n}{Unit(i) * Ans(n-i)}\) 가 됨

\(Unit(t)\) 는

• \(Unit(1) = 1, Unit(2) = 4\) 가 되고
• 그보다 큰 경우 n 이 짝수인지에 따라 3 또는 2가 됨.
• \(Unit(4)\) 라면 아래와 같음
• 

시간복잡도

O(\(n^2\))

코드

int dp[151];

int main()
{
	dp[0] = 1; dp[1] = 1; dp[2] = 5;
	for (int i = 3; i <= 150; i++)
	{
		dp[i] = dp[i - 1] + 4 * dp[i - 2];
		for(int j = 3; j <= i; j++)
			dp[i] += (j % 2 ? 2 : 3) * dp[i-j];
	}

	int n, t;
	cin >> n;
	while (n--)
	{
		cin >> t;
		cout << dp[t] << '\n';
	}
}