C++) 백준 2133번 풀이_타일 채우기

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

2133번: 타일 채우기

....

이전 타일문제들과 똑같이 풀면 되는줄 알았는데.........

후

 

일단 홀수에서는 안 구해도 되니까 0으로 제외.

 

3X2에서는

이렇게

 

DP[2] = 3

 

3X4에서는

3X2옆에 3X2가 붙는 경우 + 3X4에서만 나오는 모양 2개

DP[4] = DP[2]*3 + 2

 

그리고... 6으로 가면

DP[4] 옆에 3X2가 붙는 경우 + DP[2] 옆에 3X4가 붙는 경우 + 3X6에서만 나오는 모양 2개

 

DP[6] = DP[4]*3 + DP[2]*2 + 2

 

...이런식으로

 

DP[N] = DP[N-2]*3 + DP[N-4]*2 + 2

 

라고 생각했는데 틀렸다.

그래서 ㅅㅂ 뭐지 하고 생각해보니

 

저경우에...

 

DP[8]을 살펴보면

 

DP[8] = DP[6]의 오른쪽에 3X2가 붙는 경우 + DP[4]의 오른쪽에 3X4가 붙는 경우 + 3X8에서만 나오는 모양 2

 

와

 

DP[2]의 오른쪽에 3X6에서만 나오는 모양이 붙는 경우 2

 

까지 들어가야 한다

 

한단계 더 올라가보면

 

DP[10] = DP[8]에 3X2 + DP[6]에 3X4 + 3X10에서만 나오는모양 + DP[2]에 3X8모양 + DP[4]에 3X6모양

 

까지 계산해줘야 한다는 거다

 

 

 

....

....그것을... 코드로 짜면 됩니다.

(후에 붙인 부분을 좀 더 알아보기 쉽게 짤수 있겠는데, 지금은 하기 싫어서 패스)

 

#include<stdio.h>

int main(void) {
	int i, j, num;
	int res[31] = { 0,0,3 };
	scanf("%d", &num);
	for (i = 4; i <= num; i += 2)
	{
		res[i] = res[i - 2] * 3 + res[i - 4] * 2 + 2;
		for (j = i - 6; j > 0; j -= 2)
		{
			res[i] += res[j] * 2;
		}
	}
	printf("%d", res[num]);
}