백준 2133. 타일 채우기

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

2133번: 타일 채우기

홀수는 만들수 없으므로 n이 홀수인 경우 항상 0이고 짝수만 고려해주면 된다.

 

N = 2인 경우는 문제에서 주어지듯이 3가지 경우가 있고 이 세가지 모양이 상당히 중요하다.  d[2] = 3

 

N = 4인 경우, 3x2 타일에 3x2타일들을 붙여주면 된다. 즉 d[2] * 3이므로 d[4] = 9이다. 

그런데 문제에서 주어진 그림을 보자. 

길이 3부터 시작하는 부분 

바로 이 부분은 3x4크기 인데 위에서 구한 9가지 경우에 포함이 안된다는것을 알수 있다.

이 부분은 3x2 타일에 3x2 타일을 붙인 경우에 해당하지 않는다.

따라서 위에서 구한 9가지 경우에 이 이상하게 생긴 타일과, 뒤집은 타일 총 2가지를 더해서 d[4] = 9 + 2 = 11

 

N = 6 인 경우, N이 4인 경우에 3x2 타일을 붙인 갯수 d[4] * 3 = 33 

또한 N이 2인 경우에 위에 이상하게 생긴 3x4 크기의 타일을 붙이는 갯수 d[2] * 2 = 6 

또 N = 6일때도 이상하게 생긴 타일이 두개 추가된다.