BOJ 2133번 타일채우기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/2133/2133/%EC%86%8C%EC%8A%A4.cpp

잘 정리된 블로그가 있어 주소를 남겨봤습니다. https://mizzo-dev.tistory.com/entry/baekjoon2133

 

타일채우기 문제에는 특정한 규칙이 있습니다.

1. 2*1, 1*2 형식의 짝수형 타일이므로 N이 홀수가 되면 빈공간이 생겨 채울수 없는 문제가 발생합니다.

2. 짝수개(2)씩 늘어나는 타일채우기형이므로 짝수+짝수를 하게되면 중간부분에 특정모양이 새로 생기게 됩니다.

 

3*2 와 3*4 의 그릴 수 있는 형태만 그려보면 3*6, *8, *10,

이렇게 짝수개로 늘어날때 2개씩 특정모양이 생기게 됨을 알 수 있습니다.

3*2 를 3개로 기본값을 보고

3*4 를 채우기 위해서는 (3*2) * (3*2) + (3*4)의 고유모양 2개 = 9+2 = 11

3*6 를 채우기 위해서는 (3*2) * (3*4) + (고유모양 3*4)*(3*2) 개 + (3*6)의 고유모양 2개 = 33 + 6 + 2 = 41

3*8 를 채우기 위해서는 (3*2) * (3*6) + (고유모양 3*4)*(3*4) 개 + (고유모양 3*6) * (3*2) 개 + (3*8)의 고유모양 2개

123+25+6+2 = 153 이 됨을 알 수 있습니다.

 

#include <iostream>
using namespace std;
 
int N;
int dp[31] = { 1,0,3, };
 
int main() {
    cin >> N;
 
    if (N % 2) cout << "0";
    else {
        for (int i = 4; i <= N; i = i + 2) {
            int temp = dp[2] * dp[i - 2];
            for (int k = 4; k <= i; k=k+2) {
                temp += 2 * dp[i - k];
            }
            dp[i] = temp;
        }
        cout << dp[N];
    }
 
    return 0;
}