[알고리즘 문제해결전략] POLY - 폴리오미노

[생각의 흐름]

1. 위에서 아래로 정사각형을 x개씩 채워나간다.

2. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 칸에 채우려는 사각형의 갯수를 알면 경우의 수를 구할 수 있다.
( 윗칸에서 채운 사각형의 수 + 현재 칸을 채우려는 사각형의 수 - 1)

3. 재귀함수를 통해 모든 경우의 수를 구한다.

4. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 사용할 수 있는 남은 사각형(leftBlock)의 갯수를 통해 메모이제이션이 가능하다. 

 

 

/* https://www.algospot.com/judge/problem/read/POLY */
#include <stdio.h>
#include <memory.h>

const int MAX_BLOCK = 101;
const int MOD = 10000000;

int cache[MAX_BLOCK][MAX_BLOCK];
int n;

int sol(int leftBlock, int prevUsedBlock)
{
    if (leftBlock == 0)
        return 1;

    int &ret = cache[prevUsedBlock][leftBlock];
    if (ret != -1)
        return ret;
    ret = 0;

    for (int usedBlock = 1; usedBlock <= leftBlock; usedBlock++)
    {
        int maxShift = prevUsedBlock + usedBlock - 1;
        ret += sol(leftBlock - usedBlock, usedBlock) * maxShift;
        ret %= MOD;
    }

    return ret;
}

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

    while (C--)
    {
        memset(cache, -1, sizeof(cache));
        scanf("%d", &n);
        int ret = 0;
        for (int usedBlock = 1; usedBlock <= n; usedBlock++)
        {
            ret += sol(n - usedBlock, usedBlock);
            ret %= MOD;
        }
        printf("%d\n", ret);
    }
    return 0;
}