[백준 2133번] 타일채우기

먼저 타일을 채울 수 있는 단위타일을 만들어 보면 아래와 같다

2*3의 타일은 3개지만, 2n * 3의 타일들은 2개씩 나온다. (1<n)

---

일단 4*3의 타일을 채우는 경우를 생각해보자

위와 같이 2*3단위타일이 2개 오거나, 4*3단위 타일이 1개 올 수 있다.

D[i]를 가로의 길이가 i인타일을 채우는 경우의 수라고 하면,

2*3단위 타일이 2개인 경우는 다르게 표현하면, D[2]에 2*3단위 타일이 연속해서 오는 경우이다 (곱사건)

4*3타일이 1개인 경우는 다르게 표현하면, 가로의 길이가 0인 타일을 채운 경우인 D[0]에 4*3단위 타일이 연속해서 오는 경우이다 (곱사건)

2*3단위 타일을 만드는 경우의 수는 3가지, 4*3단위 타일을 만드는 경우는 2가지이므로

 D[4] = D[2]*3 + D[0]*2

단, 여기에서 D[0]은 0*3의 타일에 아무것도 채우지 않는 경우의 수 이므로 D[0]=1이다.

---

조금 더 확장해서 6*3의 타일을 만드는 경우를 생각해보자.

이번에는 위의 예시에서 학습한 내용을 바로 적용해보았다.

2*3단위 타일을 만드는 경우의 수는 3가지, 2n * 3단위 타일을 만드는 경우는 2가지 (단, 1<n)이므로,

D[6] = D[4]*3 + D[2]*2 + D[0]*2

---

위의 예시들을 바탕으로 점화식을 세워보면

D[n] = D[n-2] * 3 + ∑D[n-2k] * 2 ( 단, 2<2k<=n, n은 2<n인 짝수 ), D[2]=3, D[0]=1

D[n] = 0 ( n은 홀수 )

---

#include <bits/stdc++.h>
#define MAX 30

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin>>n;
  int d[MAX+1]={0,};
  d[0]=1;
  for(int i=1; i<=n; i++){
    if(i%2==0){
      if(i>=2) d[i]+=d[i-2]*3;
      if(i>=4){
        for(int j=4; j<=i; j+=2){
          d[i]+=d[i-j]*2; 
        }
      }
    }
  }
  cout<<d[n];
}