2133 타일 채우기

2 * n일때는 쉽게 풀었는데 3 * n은 또 모르겠다.

 

이렇게 굴러가는구나! 식이 잘 안 세워짐

 

 

홀수인 경우는 제외했다 

 

홀수는 어떻게 해도 구할 수 업슴

 

다음으로 저렇게 덩어리로 생각해보면 이전에 구했던 사이즈를 활용하면 되겠다 싶었다.

 

그런데 문제는 겹치는 경우가 자꾸 있음 ㅠㅠㅠ

 

2 + 2 + 2 + 2 전부 2로 이루어진 경우가 자꾸 겹친다...

 

숫자가 커질 수록 많이 겹치는 2 + 2 + 2 .. 들

 

그 다음 생각한 건 전부 2로 이루어진 경우를 제외하고 숫자를 센 다음 마지막에 2 + 2 + 2 .. 경우 하나를 합해주면 어떨까? 싶었음

 

 

하지만 겹치는 건 2 +2 +2 .. 들만의 문제는 아니었다....

 

사진 보면 2 + 4 + 2도 겹침ㅋㅋㅋ ㅠ 모르겠다 ㅠ 

 

---

홀수 일 경우에는 구할 수 없으므로 0을 반환하고

짝수 일 경우를 생각하면 이런 규칙이 보인다

 

2일 경우 3가지 4일 경우 2가지 6일 경우 2가지..

 

이렇게 새로운 타일이  나타난다.  쓰고보니 새로운 타일이라기 보다는 딱 고정된? 나눌 수 없는 타일

 

이제 크기 2 타일을 배치하고, 4타일을 배치하고, 6 타일을 배치하고 ... 타일을 배치하면서 갯수를 세주면 된다.

 

 

3* f(n-2) +2f(n-4) + 2f(n-6) + ...

 

식을 세워보면 위처럼 나온다.

 

이해하는데 많이 힘들었던 문제 ㅠ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int cache[35];

int     func(int n)
{
    if (n % 2 == 1)
        return 0;
    if (n == 0)
        return 1;
    if (n == 2)
        return 3;

    int& ret = cache[n];
    if (ret != -1)
        return ret;
    ret = 3 * func(n - 2);
    for (int i = n - 4; i >= 0; i -= 2)
        ret += 2 * func(i);
    return ret;
}

int     main()
{
    int n;
    scanf("%d", &n);

    memset(cache, -1, sizeof(cache));

    printf("%d\n", func(n));

    return 0;
}