2133(타일 채우기)

난이도: 골드 4

 

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

문제

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

입력

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

출력

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

 

풀이

 

N = 4일 때, 특이 케이스

 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
#define MAX 31

int N;
int dp[MAX];

int main()
{
	cin >> N;

    // 홀수일 때는 채울 수 없음
    memset(dp, 0, sizeof(dp));
    
    dp[0] = 1;  // 특이 케이스 2가지를 더하는 점화식. 즉, F(0)*2를 이용하기 위함
    dp[2] = 3;
    // 점화식 F(N) = F(N - 2) * 2 + F(N - 4) * 2 + ... + F(2) * 2 + F(0) * 2
    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] += dp[j] * 2;
    }

    cout << dp[N];
}