[algospot] POLY

문제링크 입니다

손도 대지못했습니다 ㅜ^ㅜ. 폴리오미노 라는 말을 처음 들었고, 이해하는것도 힘들었습니다. 문제집을 참고했습니다.

[POLY] 문제 😭😭😭😭😭

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 그 후 각 줄에 폴리오미노를 구성할 정사각형의 수 n (1≤n≤100)이 주어집니다.

출력

각 테스트 케이스마다, n개의 정사각형으로 구성된 세로 단조 폴리오미노의 수를 출력합니다. 폴리오미노의 수가 10,000,000 이상일 경우 10,000,000으로 나눈 나머지를 출력합니다.

입력 예제

3
2
4
92

출력 예제

2
19
4841817

전체 코드는 다음과 같습니다.

//
//  POLY.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/28.
//

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int MOD = 10000000;
ifstream fin("POLY.txt");
int cache[101][101];
/*
n : n개의 사각형으로 이루어짐.
first : 맨 윗줄의 사각형의 수
return 폴리노미아 수
*/
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;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        int sum=0;
        int n=0;
        fin >> n;
        memset(cache,-1,sizeof(cache));
        for (int j = 1; j <= n; j++){
            sum += POLY(n, j);
            sum %= MOD;
        }

        cout << sum << endl;
    }
    return 0;
}