[동적계획법] 12. 폴리오미노

폴리오미노

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

algospot.com :: POLY

 

컨셉

폴리오미노를 만드는 문제를 두 단계로 나눴다. 

1. 사각형 배분하기

2. 사각형 위치잡기

 

윗줄에 a, 바로 아래줄에 b개의 사각형이 놓여있다면 위치를 잡는 방법의 수는 a+b-1개.

 

poly(int n, int first) //n개의 사각형으로 만드는 폴리오미노의 개수. 단 맨 윗줄에는 first개를 놓는다.

→ poly(n, first) = ( first + 두번째놓는거 사각형 수 - 1 )   //2. 위치잡기

                      * poly(n-first, 두번째 놓는거 사각형 수)  //1. 나머지 사각형 배분하기

초안

내 답안 (정답, 16ms)

 

/**
 * @name    8.14.폴리오미노
 * @ID      POLY
 * @date    2019-08-12
 * @author  Sunmon
 */
 
 
//FIXME: input : 92일때 틀림
 
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 10000000;
int cache[100+1][100+1];
int N;
// n개의 사각형으로 폴리오미노를 만드는 방법의 수 리턴. 첫줄에는 first개의 사각형을 놓는다.
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 i =1; i<= n - first; i++)
    {
        //temp: 위치를 바꾸는 방법의 수 * 놓고 나머지 남은 사각형으로 폴리오미노륾 만드는 방법의 수
        int place = first + i - 1;
        int nextPoly = poly(n-first, i);
        int temp = (place * nextPoly) % MOD;
        ret += temp;
        ret %= MOD;
    }
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
 
    int N;
    while(C--)
    {
        memset(cache, -1, sizeof(cache));
        cin >> N;
 
        int answer = 0;
        for(int i = 1; i<= N; i++)
        {
            answer = (answer + poly(N, i)) % MOD;
        }
        cout << answer << endl;
 
    }
}

 

주의

마지막 정답 구할때도 MOD 할 것!!!!!!!!!

MOD쓰는 문제는 마지막까지 방심하지 말자.