8_14.cpp

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 10 * 1000 * 1000;
long long poly(vector<vector<long long>> D, int N) {
	for (int n = 1; n <= N; n++) {
		for (int down = 1; down <= n; down++) {
			for (int i = 1; i <= n - down; i++) {
				D[n][down] += D[n - down][i] * (down + i - 1);
			}
			if (n == down)
				D[n][down] = 1;
			D[n][down] %= MOD;
		}
	}

	long long ans = 0;
	for (int down = 1; down<= N; down++) {
		ans += D[N][down];
		ans %= MOD;
	}

	return ans ;
}

int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n; cin >> n;
		vector<vector<long long>> D(101, vector<long long>(101));
		cout << poly(D, n) << endl;;
	}
	return 0;
}

문제 정의 : 세로 단조를 만족 시키면서 폴리노미오 도형 갯수 찾기 (중복 되지 않는 모형 갯수 찾기)
풀이 방법: 동적 프로그래밍
개선 사항: 밑 면 갯수를 기준으로 기존에 구했던 도형 갯수를 중첩 시켜 구할 수 있음을 빨리 캐치할 수 있어야 한다. mod = 10000000 조건이 주어진 것을 확인해도 동적 프로그래밍 문제임을 파악할 수 있어야 한다.

다른 풀이

#pragma once
#include<cstdio>
#include<cstring>
 
int poly[101][101] = { 0 };
const int MOD = 10000000;
 
int getPOLY(int nums, int down)
{
    int& ret = poly[nums][down];
 
    if (nums == down)
    {
        return ret = 1;
    }
 
    if (ret != -1) return ret;
 
    ret = 0;
 
    int blocks = nums - down;
    for (int i = 1; i <= blocks; i++)
    {
        ret += (i + down - 1) * getPOLY(blocks, i);
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        int n;
        scanf("%d\n", &n);
 
        memset(poly, -1, sizeof(poly));
 
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            res += getPOLY(n, i);
            res %= MOD;
        }
 
        printf("%d\n", res);
    }
 
    return 0;
}

https://sangdo913.tistory.com/41