[알고스팟] 폴리오미노(POLY)

문제 정보

시간 : 1000ms
제한 메모리 : 65536kb

문제

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

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

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

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

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

예제 입력

3 2
4 92

예제 출력

2 19
4841817

소스

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Poly {

    public static int N;
    public static final int MOD = 10*1000*1000;
    public static int[][] cache;

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        System.setIn(new FileInputStream("D://sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine().trim());
        for(int testCase=1; testCase <= T; testCase++) {

            N = Integer.parseInt(br.readLine().trim());

            cache = new int[101][101];

            for(int i=0; i<101; i++) {
                for(int j=0; j<101; j++) {
                    cache[i][j] = -1;
                }
            }

            int result = 0;
            for(int i=1; i<=N; i++) {
                result += poly(N,i);
                result %= MOD;
            }


            bw.flush();
            bw.write(result + "\n");


        }

        bw.close();

    }

    public static int poly(int n, int first) {
        // 기저 사례: n == first
        if(n==first) {
            return 1;
        }
        // 메모이제이션
        if(cache[n][first] != -1) {
            return cache[n][first];
        }

        int 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;
        }

        cache[n][first] = ret;

        return ret;

    }

}

풀이

제일 위 가로줄에 포함할 정사각형의 수 first,
따라서 poly(n, first)는 n개의 정사각형으로 첫줄에 first개의 정사각형으로 이루어진 폴리오미노 수.
모든 정사각형은 붙어 있어야 하므로(세로 단조 폴리오미노) 첫줄에 가능한 경우의 수는 n.
결국 poly(n, first) = first * (poly(n-first, 1) + poly(n-first, 2) + … + poly(n-first, n-first).
하지만 두번째 줄의 정사각형 개수에 따라 붙일 수 있는 방법의 수가 정해진다.
First + second -1 이 첫째줄과 둘째줄을 붙일 수 있는 경우의 수이다.
따라서 이렇게 정의할 수 있다.
Poly(n, first) = (second + first - 1) * (poly(n-first, 1) + poly(n-first, 2) + … + poly(n-first, n-fisrst))