[C++]2133번 타일 채우기

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

접근

점화식을 구해 쉽게 풀 수 있다
$dp[N]=3(dp[N-2])+2+ \displaystyle\sum_{N=0}^{N=N-4}{dp[N]}$
이때 N이 홀수일 때는 제외시킨다

코드

#include <iostream>
using namespace std;

int main(){
    long long dp[31];
    dp[2] = 3;
    for(int i = 4; i <= 30; i += 2) {
        dp[i] = (dp[i - 2] * 3) + 2;
        for(int j = i - 4; j > 0; j -= 2) dp[i] += dp[j] * 2;
    }
    int n;
    cin >> n;
    if(n % 2 == 1) cout << 0;
    else cout << dp[n];
}