BOJ - 2133번 타일 채우기

www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

3x홀수 인 경우에는 만들 수가 없으므로 다 0이다.

 

DP[2] = 3이고

 

DP[4] = 11이다.

 

2개짜리 2개를 붙여서 만들 수 있으므로 3x3인데 특이케이스가 2개가 더 생겨서 11이 된것이다.

 

DP[6]도 그려보면 4개짜리에 2개짜리를 붙인 11x3개를 제외하고 특이케이스가 2개가 더 생긴다.

 

근데 우리가 놓친 특이케이스가 또 있다.

 

11x3은 4개짜리 오른쪽(혹은 왼쪽)에 2개짜리를 붙이는 경우를 뜻하는데

 

대부분의 경우는 좌우대칭이 고려되나 4개짜리를 계산할 때 나타난 특이케이스에 대해서는 고려가 안된다.

 

그 특이케이스 2개에 대해서 왼쪽(혹은 오른쪽)에 다시 2개를 붙여줘야한다.

 

따라서 DP[6] = 3*DP[4] + 2*DP[2] + 2 = 41이 된다.

 

DP[8]을 보자.

 

6개짜리에 2개를 붙인다 => 3*DP[6]

 

6의 특이케이스 2개에 대해서 반대편에 2개를 붙여준다. => 2*DP[2]

 

4의 특이케이스 2개에 대해서 반대편에 4개를 붙여준다. => 2*DP[4]

 

따라서 DP[8] = 3*DP[6] + 2*DP[2] + 2*DP[4] + 2 = 153

 

마지막으로 DP[10]을 보자.

 

8개에 2개 붙여주고 => 3*DP[8]

 

8의 특이케이스 2개에 대해서 반대편에 2개 => 2*DP[2]

 

6의 특이케이스 2개에 대해서 반대편에 4개 => 2*DP[4]

 

4의 특이케이스 2개에 대해서 반대편에 6개 => 2*DP[6]

 

그리고 10개에 대한 특이케이스 2개

 

따라서 DP[10] = 3*DP[8] + 2*DP[2] + 2*DP[4] + 2*DP[6] + 2 = 571

 

 

점화식을 세워보자

 

i는 짝수일 때만 고려해서

 

DP[i] = 3*DP[i-2] + (2*DP[i-4] + 2*DP[i-6] ... 2*DP[4] + 2*DP[2]) + 2

 

마지막에 2가 마음에 안드니까 DP[0]에 1을 대입한다면

 

DP[i] = 3*DP[i-2] + (2*DP[i-4] + 2*DP[i-6] ... 2*DP[4] + 2*DP[2] + 2*DP[0])

 

코드는 다음과 같다.

 

 

/* BOJ - 2133번 타일 채우기 문제 */

#include 

int N, DP[31];

// 초기화 및 입력 함수
void init() {
	for (int i = 0; i < 31; i++) DP[i] = 0;
	scanf("%d", &N);
}

// 계산 함수
void cal() {
	DP[0] = 1;
	DP[2] = 3;
	for (int i = 4; i <= N; i++) {
		if (i % 2 == 1) continue;
		DP[i] = 3 * DP[i - 2];
		for (int j = 0; j < i - 2; j++) {
			if (j % 2 == 1) continue;
			DP[i] += 2 * DP[j];
		}
	}
	printf("%d\n", DP[N]);
}

// 메인 함수
int main() {
	init();
	cal();
	return 0;
}