Baekjoon2133-타일 채우기

백준 사이트 2133 - 타일 채우기 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

dp문제입니다. 기존 타일 문제과 달리 해줘야할 전처리들이 있습니다. 백준에서는 Sliver2의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

1. 홀수인 경우 타일을 채울 수 없습니다. 직접그려보면 알 수 있습니다.
2. n이 4 이상인 경우 새로운 타일들이 생겨납니다.

구상도는 밑과 같습니다.

• (1)에서 특수한 경우만 세주는 이유는 특수한 경우가 아닐 경우 3 * 2 + 3 * 2 + 3 * 2 로 나눠지므로 이는 다시 3 * 2 + 3 * 4로 합쳐지므로 사실상 (2)에서 이미 세졌기 때문입니다.

---

5. code

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int dp[31] = { 1,0,3,0 };
	for (int i = 4; i <= n; i+=2)
	{
		//일반적인 case
		dp[i] = dp[i - 2] * 3;
		for (int j = 4; i - j >= 0; j += 2)
		{
			dp[i] += dp[i - j] * 2;
		}	
	}
	cout << dp[n];
}

---

6. 후기

타일 채우기에 좀 익숙해진 것 같다.