[C++] 백준 2133 - 타일 채우기

문제 링크

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

2133번: 타일 채우기

 

 

3 X n 타일링이기 때문에 n이 홀수인 경우 타일을 다 채울 수 없습니다.

 

이전 타일링 문제들과 동일하게 n 이전 값들의 모형에서 다른 모형이 붙은 규칙은 동일합니다.

하지만 n이 4 이후부터는 고유의 모형이 위 그림과 같이 생기게되는데 그렇다고 2만 더해준다고 답을 구할수 없습니다.

정확히는 n이 0인 상태에서 2개의 모형이 추가로 붙은 형태이기 때문에 n이 0인 상태에서 2를 곱해준 값을 더해야합니다.

 

n이 6일 때는 n이 4일때의 모형 * 3 가지 방식과

n이 2일때의 모형에 n이 4일때의 두가지 고유 모형을 추가해주는 방식,

n이 0일때의 모형에 n이 6일때의 두가지 고유 모형을 추가해주는 방식을 더해주게 됩니다.

 

따라서 점화식은 d(n) = d(n-2) * 3 + d(n-4) * 2 + d(n-6) * 2 + ... 으로 구할 수 있습니다.

 

 

구현 코드