[c언어/c++] 폴리오미노 POLY 경우의수, 동적계획법

정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.

예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아닙니다.

n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작성하세요.

문제 전체 - https://algospot.com/judge/problem/read/POLY

#include<stdio.h>

#include<memory.h>

#define MOD 10000000

int n;

int cache[120][120];

int poly(int,int);

int main(){

int c;

scanf(" %d",&c);

while(c-- > 0){

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

scanf(" %d",&n);

int start = 0;

int ans = 0;

for(int i = 1 ; i < n ; i++){

ans = ans + poly(n,i);

ans %= MOD;

}

printf("%d\n",ans+1);

}

return 0;

}

int poly(int n,int first){

if(n == first) return 1;

int &ret = cache[n][first];

if(ret != -1) return ret;

ret = 0;

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;

}