[백준 2133] 타일 채우기

0. 제목

• 백준 2133 타일 채우기
• BOJ 2133 타일 채우기
• C++ 2133 타일 채우기

---

1. 문제

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

---

2. 풀이

• 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 것이다.
• 앞서 풀었던 타일 채우기 문제와는 살짝 달랐다.
• 앞에서 풀었던 타일 문제들은 N의 값이 늘어날 때 새로운 종류의 타일 모양이 나오지 않았다.
• 그러나 이 문제는 N이 2씩 늘어날때마다 새로운 모양 2개가 추가적으로 생겼다.
• 먼저 끝 2칸을 제외하면 3가지 방법이 나온다. 그리고 4칸, 6칸, 8칸.... 제외하면 2가지씩 추가적으로 생긴다.
• 그리고 3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다. N이 홀수이면 넓이가 짝수인 타일들로는 채울 수 없기 때문이다.
• 그래서 N이 홀수인 경우 dp[N] = 0 이다.
• 따라서 N에 대하여 점화식을 써보면 다음과 같다.
• dp[N] = 3*dp[N-2] + 2*dp[N-4] + 2*dp[N-6] + 2*dp[N-8] + ... + 2*dp[0]

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int dp[31];
    cin >> N;
    dp[0] = 1;
    dp[2] = 3;
    if(N % 2 == 1)
        dp[N] = 0;
    else{
        for(int i = 4; i <= N; i += 2){
            dp[i] = 3 * dp[i-2];
            for(int j = 4; j <= i; j += 2){
                dp[i] += 2 * dp[i - j];
            }
        }
    }
    cout << dp[N] << '\n';
    return 0;
}