C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 2133번:타일채우기 답

//3xn을 채우는데 1x2,2x1 타일로 총 세가지로 채울 수 있다.

//가짓 수 : D[n] - > n이 짝수여야지만 주어진 타일로 채울 수 있다.

//D[i] = 3*D[i-2]+2*D[i-4]+2*D[i-6]....+2*D[i-2*j]

//D[i] = 3*D[i-2]+2*sum[i-4]라고 나타낼 수 있다.

#include <iostream>
using namespace std;
int n,d[31];
int main() {
    cin >> n;
    d[0] = 1;
    for (int i = 2; i <= n; i+=2)
    {
        d[i] = 3 * d[i - 2];
        for (int j = 0; j <= i - 4; j += 2)
            d[i] += 2 * d[j];
    }
    cout << d[n] << '\n';
}