[POLY] 폴리오미노

[POLY] 폴리오미노 : https://algospot.com/judge/problem/read/POLY

### DP ###

< 소스코드 >

poly(up, n) : 윗층에 up개의 블럭이 쌓여있을 때, n 개로 폴리오미노를 만들 수 있는 방법의 수.

#include <stdio.h>
 
const int MOD = 10000000;
 
int d[101][101];
 
int poly(int up, int n)
{
    int ret = 0;
    if(n == 0) return 1;
    if(n == 1) return up;
    if(d[up][n]) return d[up][n];
 
    for(int down=1; down<=n; down++) {
        ret += (poly(down, n-down)*(up+down-1));
        ret %= MOD;
    }
    return d[up][n] = ret; 
}   
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, ans=0;
        scanf("%d", &n);
 
        for(int i=1; i<=n; i++) {
            ans += poly(i, n-i);
            ans %= MOD;
        }
        printf("%d\n", ans);
    }
     
    return 0;
}

>> 15 : 곱해줘야하는데, 더해서 시간을 많이 소비했다....