백준 2133(타일 채우기) c++

문제

2133번: 타일 채우기

3 * n 행렬을 (2*1) 타일과 (1*2) 타일로 채우는 경우의 수를 구하는 문제입니다.

위의 예시는 n =12 인데 이런식으로 채우면 됩니다.

생각해 보면 n =홀수 이면 타일을 채울 수 없습니다.

먼저 n = 2이면 총 3가지로 타일을 채울 수 있습니다. 따라서 dp[2] = 3입니다.

 n = 4이면 반으로 갈라서 dp[4] = dp[2] * dp[2] 일거 같지만, 아닙니다.

특별한 경우가 있습니다.

위의 두가지 경우의 수는 dp[2]의 타일들로 만들 수 없습니다.

따라서 dp[4] = dp[2] * dp[2] + 2 = 11입니다.

그러면 dp[6]은 어떨 까? dp[6] = 2*(dp[4]*dp[2]) + 2 일까?

그렇지 않습니다.

결론만 말하면 중복되는 경우의 수가 많기 때문입니다. 

저는 이 블로그를 참고 하여 해결하였습니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
ll dp[31];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 0;
    dp[2] = 3;
    for (int i = 3; i <= n; i++)
    {
        if (i % 2 == 1)
            dp[i] = 0;
        else
        {
            dp[i] = dp[i - 2] * dp[2];
            for (int j = i - 4; j >= 2; j--)
            {
                dp[i] += dp[j] * 2;
            }
            dp[i] += 2;
        }
    }

    cout << dp[n];
    return 0;
}