백준 2133: 타일 채우기

조오금 까다로운 문제다. 강의노트가 없었다면 아마 꽤 시간을 많이 걸렸거나 못 풀었을 것 같다. 아이디어만 캐치하면 코딩자체는 심플하고 쉽다. i가 i번째에서의 블록 개수라고 하면 i-2 에서 블록 3개를 가지고 i와 i-2사이의 3x2공간을 채우는 경우를 생각해보면 3가지 경우가 있고 점화식이 생각난다. 하지만 여기서 끝이 아니라 i - 4, i - 6, .. 계속 나아가 심지어 0일 때 조차도 블록을 쌓을 수 있는 경우가 있는데 블록들을 2층으로 쭉 쌓고 그 부분을 감싸는 형태의 모습이다. 이 블록은 2칸 마다 새로운 형태의 블록이기 때문에 따로 점화식을 세워줘야 한다.

#include <iostream>
long long d[50];
//n은 짝수일 수 밖에 없다.
int main()
{
    int input = 0;
    std::cin >> input;
    d[0] = 1;
    for (int i = 2; i <= input; i = i + 2)
    {
        d[i] = d[i - 2] * 3;
        for (int j = 4; j <= i; j = j + 2)
        {
            d[i] += d[i - j] * 2;
        }
    }
    std::cout << d[input] << std::endl;
    return 0;
}