[python] algospot POLY 문제풀이

문제

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

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

-> 문제 링크 : https://algospot.com/judge/problem/read/POLY

algospot.com :: POLY

 

문제풀이

문제에서 제시되는 조건을 살펴보면 아래와 같이 2가지가 있다.

1. 폴리노미오에서는 반드시 i층의 일부가 i-1층의 부분과는 연결이 되어있어야 한다.

2. i층에서 i+1층으로 가려면 무조건 한 개의 블록은 있어야 한다.

3. 또한 세로 단조라는 조건이 있기에 i층의 블록들은 무조건 서로 연결되어 있어야 한다.

 

현재 줄에 블록이 연결되어 만들어져 있을 때, 다음 줄에 모형은 현재 줄의 블록에 영향을 받는다. 그렇기에 이 문제를 현재 줄에 블록이 n개 있을 때, 블록 m개를 가지고 밑에 붙여지는 도형을 만드는 경우의 수를 세는 문제로 생각할 수 있다.

 

이렇게 보면 기준을 (현재 줄에 블록 수, 남은 블록 수)로 잡고 문제를 쪼갤 수 있다.

i층에서 (N,M)이라면 i+1층에서는 생길 수 있는 블록의 개수는 다음과 같다.

i+1층의 블록 개수가 1개인 경우 : (1,M-1)

i+1층의 블록 개수가 2개인 경우 : (2,M-2)

i+1층의 블록 개수가 3개인 경우 : (3,M-3)

i+1층의 블록 개수가 M개인 경우 : (M,0)

 

즉 하나의 층 당 남은 블록 개수만큼의 부분 문제가 만들어진다.

하지만 메모이제이션을 활용하면 제한 시간 안에 해결이 가능하다.

 

폴리노미오를 몇 개 만들다 보면 두 층이 합쳐질 때 결합되는 방법의 수는 패턴을 갖고 있다는 것을 찾을 수 있다.

만약 위층의 블록 개수가 a개이고, 밑층의 블록 개수가 b개라면 두층이 합해져 만들어지는 폴리노미오의 개수는 a+b-1이 된다.

위에서 쪼갠 부분 문제는 각 층의 블록의 개수에 따른 경우의 수니까 두 층이 합쳐질 때마다 (a+b-1)을 곱해줘야 한다.

 

코드

1. python

import sys

T = int(sys.stdin.readline().rstrip())

def polynomio(now, block) :


    if block == 0 :
        return 1

    if dp[now][block] :
        return dp[now][block]

    cnt = 0

    for i in range(1, block+1) :
        cnt += ( polynomio(i, block-i) * (now+i-1) ) % 10000000
    dp[now][block] = cnt
    return cnt


for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())

    dp = [ [ None for _ in range(N+1)] for _ in range(N+1) ]

    answer = 0
    for i in range(1, N+1) :
        answer = ( answer + polynomio(i,N-i) ) % 10000000

    print(answer % 10000000)

2. c++

#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 10000000;
int cache[101][101];


int polyomino(int now, int block)
{
    if(block == 0) return 1;

    int& ret = cache[now][block];
    if(ret != -1) return ret;

    ret = 0;
    int cnt = 0;
    for(int i =1; i<=block; i++)
    {
        cnt += ( poly(i, block-i) % MOD * (now+i-1) ) % MOD;
    }
    ret = cnt;
    
    return ret;
}

int main()
{
    int C;
    int N;
    
    cin >> C;
    
    while(C--)
    {
        memset(cache, -1, sizeof(cache));
        cin >> N;

        int answer = 0;
        for(int i = 1; i<= N; i++)
        {
            answer = (answer + polyomino(i, N-i)) % MOD;
        }
        cout << answer % MOD << endl;

    }
}

 

파이썬 코드에서는 시간 초과가 나오지만 똑같은 로직으로 C++ 코드로 변환해서 돌리면 통과한다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.