BOJ 2133 타일 채우기

boj 2133 타일 채우기

n이 홀수일 때, 타일을 전부 채울 수 있는 방법은 없다. 그러므로 n이 짝수일 때만 살펴보면 된다.
테이블 D[i]를 n이 i일 때, 타일을 전부 채울 수 있는 방법 수라고 정의하자.
타일이 2칸일 때 채울 수 있는 방법의 수가 3가지인 것은 쉽게 알 수 있다. 그리고 힌트를 보면 4칸의 경우 2칸인 경우를 이용하지 않고 채우는 방법이 2가지가 있다는 것을 알 수 있다. 이 사실만으로 간단하게 점화식을 D[i] = D[i-2]x3 + D[i-4]x2 라고 하면 틀린다.

위의 사진을 보면, 타일이 2칸씩 늘어날 때마다 채우는 방식 2가지가 추가된다. 이를 바탕으로 점화식을 구현해보자.

D[i] = D[i-2]x3 + D[i-4]x2 + D[i-6]x2 + ... + D[0]x2

위 내용을 기반으로 구현한 코드를 보자.

#include <iostream>
using namespace std;

int n;
int D[35];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    D[0] = 1;
    D[2] = 3;

    if (n % 2 == 0)
    {
        for (int i = 4; i <= n; i = i + 2)
        {
            D[i] = D[i - 2] * 3;

            for (int j = 4; j <= i; j = j + 2)
            {
                D[i] += D[i - j] * 2;
            }
        }
    }

    cout << D[n];
}