[C++] 알고스팟/동적계획법 - 폴리오미노

문제 링크

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

algospot.com :: POLY

 

세로로 단조인 폴리오미노는 각 행의 사각형들이 모두 연속해서 붙어있어야 합니다.

같은 행에서 사각형들 사이에 공간이 있으면 안된다는 것을 의미합니다.

 

이 형태의 폴리오미노를 구하기 위해서는

첫 번째 행부터 내려가면서 각 행에서 사각형을 놓을 수 있는 모든 방법을 세어주면 됩니다.

n이 3일 때 첫 번째 행에 올 수있는 사각형은 1, 2, 3개로 총 3가지 경우가 올 수 있습니다.

 

첫 번째 행의 사각형 개수를 정하면 두 번째 행으로 내려가서 1개부터 남은 사각형 만큼을 놓고 다시 아래 행을 내려가는 방식으로 마지막 행까지 모두 구해야 합니다.

 

 

사각형을 놓는 방법은 윗 행의 사각형 개수에 영향을 받습니다.

첫 번째행의 사각형 개수가 a개가 놓여있고 두 번째 행에 사각형을 b개 놓을 때 a + b - 1 가지 방법만큼 올 수 있습니다.

 

따라서 다음 행으로 내려갔을 때의 모든 방법의 수에 현재 행에서 사각형을 놓는 방법의 수 만큼을 곱해줘야 합니다.

그리고 이를 사각형 1개를 놓았을 때 부터 남는 사각형만큼을 놓았을 때의 모든 방법을 더해주면 답을 구할 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#include <cstring>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MOD = 10000000;
	int cache[101][101];
	int poly(int n, int first){
	if(n == first) return 1;
	int &ret = cache[n][first];
	if(ret != -1) return ret;
	ret = 0;
	//현재 행에 사각형을 1개부터 남는 사각형만큼 놓는 경우를 모두 구해서 더해준다.
	for(int second=1;second<=n-first;++second){
	//바로 윗 줄에 first개의 사각형이 놓여있을 때
	//현재 줄에 second개의 사각형을 놓으려면
	//second + first - 1가지 방법만큼 놓을 수 있다.
	int add = second + first - 1;
	//다음 행에서 올 수 있는 방법을 add 개수만큼 곱해준다.
	add *= poly(n-first, second);
	add %= MOD;
	ret += add;
	ret %= MOD;
	}
	return ret;
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	memset(cache, -1, sizeof(cache));
	int n;
	cin >> n;
	int sum = 0;
	for(int i=1;i<=n;i++){
	sum += poly(n,i);
	sum %= MOD;
	}
	cout << sum << endl;
	}
	}

view raw poly.cpp hosted with ❤ by GitHub