폴리오미노(POLY)

https://algospot.com/judge/problem/read/POLY

이 문제는 그냥 책을 바로 보았다.

도저히, 풀 수가 없는 문제였다.

그리고, 책의 풀이를 보고 충격을 먹었다.

이렇게 풀 수 있구나..

이 문제 또한 계속해서 다시 풀어볼 문제이다.

참고로, 67번 째출에서 sum을 누적하며 더하면서 1000만이 넘을 수 있기 때문에

sum %= MOD를 써줬다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define MOD 10*1000*1000
 
int cache[101][101] = { 0, };
/*
n개의 정사각형으로 이루어져있고, 맨 위 가로줄에 first개의
정사각형을 포함하는 폴리오미노의 수를 반환한다. [n][first]
*/
 
// poly()의 반환값은 1천만 미만이고, (second + first -1)은 N이하이므로, 최대 10억. (int 내)
 
int poly(int n, int first)
{
    // 기저 사례 : n == first
    if (n == first) return 1;
 
    int & ret = cache[n][first];
 
    if (ret != -1) return ret;
 
    ret = 0;
 
    // poly(n, first) = ∑(second + first - 1) * poly(n - first, second);
 
    for (int second = 1; second <= n - first; second++)
    {
        int add = second + first - 1;
 
        add *= poly(n - first, second);
 
        add %= MOD;
        ret += add;
        ret %= MOD;
    }
 
    return ret;
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        int N = 0;
 
        fill(&cache[0][0], &cache[100][101], -1);
 
        scanf("%d", &N);
 
        int sum = 0;
 
        for (int i = 1; i <= N; i++) sum += poly(N, i); sum %= MOD;
 
        printf("%d\n", sum);
    }
 
    return 0;
}