백준[2133번] 타일 채우기

참고자료: https://yabmoons.tistory.com/536

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

사용되는 알고리즘 : dp

* 특별한 경우를 잘 확인해야한다. => 이전 타일을 이용해서 쌓아가는 걸 제외하고 특별한 모양

* n이 홀수일 경우는 애초에 고려하지 않는다. => 3 * odd의 경우 넓이는 홀수값이 되는데 2*1 또는 1*2로 채우는 경우는 값이 무조건 짝수가 나와야 한다.

#include <iostream>
using namespace std;

int dp[31];

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    dp[0] = 1;
    dp[2] = 3;

    if (n % 2 == 1)
    {
        cout << 0;
        return 0;
    }

    for (int i = 4; i <= n; i += 2)
    {
        dp[i] = dp[i - 2] * dp[2];

        for (int j = i - 4; j >= 0; j -= 2)
        {
            dp[i] += 2 * dp[j];
        }
    }

    cout << dp[n];

    return 0;
}

참고자료에 올린 블로그에서 설명을 자세하게 해주어서 이해하는데 많은 도움이 되었다.