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

1. 문제의 변형

 

n개의 정사각형으로 모든 경우의 도형을 만들 수 있는 수는

구하기가 까다롭다.

 

하지만 문제는 세로로 단조인 폴리오미노를 구하라는 것이므로

쉽게 문제를 변형하여 풀 수 있게된다.

 

세로로 단조인 폴리오미노는 가로의 직사각형으로만으로 모든

경우의 수를 구할 수 있음을 나타낸다.

 

즉, 이문제 는 탑쌓기로 변형할 수 있는데

 

1층에 몇개의 정사각형을 쓰는지

2층에 나머지 정사각형에서 몇개를 쓰는지

.

.

.

n층에 몇개를 쓰는지

 

결국 이문제는 재귀 호출로 문제를 풀 수 있게 된다.

 

2. 점화식

 

이 문제를 풀 점화식은

 

poly(remain, before) = remain만큼 정사각형이 남아있는 단계에서 before의 개수가 이전에 쓰인 경우의

                              세로 단조인 폴리오미노의 개수

 

move = 1 (before = 0)

move = before + i -1 (before < 0)

                                         

 

3. 코드

 

#include <iostream>
#include <vector>
#include <cstring>
 
const int MOD = 10*1000*1000;
 
int cache[101][101];
 
int poly(int remain , int before)
{
    int &ret = cache[remain][before], move = 0;
 
    if(ret != -1) return ret;
    if(remain == 0) return 1;
 
    ret = 0;
    for(int i = remain; i >= 1; i--)
    {    
        move = before + i - 1;
        if(before == 0)
            ret = (ret + poly(remain - i, i))%MOD;
        else 
            ret = (ret + move * poly(remain - i, i))%MOD;
    }
    return ret;
}
 
int main(void)
{
    int testCase = 0;
    int n = 0;
    
    memset(cache, -1, sizeof cache);
    std::cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        std::cin>>n;
        std::cout<<poly(n, 0)<<std::endl;
    }
}

4. 반성

 

 문제를 변형하는 방법을 책에서 읽지 않았더라면 하루안에 문제를 풀지 못햇을 것이다.

여러 측면에서 문제를 생각해야겠다.

 

 

POLY