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

 
#include <iostream>
 
int dp[31] = {};
 
int main()
{
    int n = 0;
    std::cin >> n;
 
    if (n % 2 == 1)
    {
        std::cout << 0;
        return 0;
    }
 
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
 
    for (int i = 4; i <= n; i += 2)
    {
        dp[i] = dp[i - 2] * 3;
 
        for (int j = 4; i - j >= 0; j += 2)
        {
            dp[i] += dp[i - j] * 2;
        }
    }
 
    std::cout << dp[n];
    return 0;
}

규칙

4개 -> 2개 * 3 + 4개 2

6개 -> 4개 * 3 + 2개 * 2 + 6개 2

8개 -> 6개 * 3 + 4개 * 2 + 2개 *2 + 8개 + 2