3장 다이나믹 프로그래밍 - (5) 문제 풀이 2 [2133번 - 타일 채우기]

#include <iostream>

using namespace std;

int d[31];

int main(void){

    int n;

    cin >> n;

    // d[n]=3*d[n-2]+2*d[n-4]+2*d[n-6]+...+2*d[0]

    d[0]=1;

    d[2]=3;

    for(int i=4;i<=n;i+=2){

        d[i]=3*d[i-2];

        for(int j=2;2*j<=i;j++){

            d[i]+=2*d[i-2*j];

        }

    }

    cout << d[n] << endl;

    return 0;

}