[알고스팟] 폴리오미노

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • POLY
  • 1000ms
  • 65536kb
  • 1678
  • 1071 (63%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(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

어떻게 풀까?

이 문제에서 가장 주목해야할 부분은 '세로로 단조'라는 부분과 폴리오미노가 '정사각형들의 변들을 서로 완전하게 붙여 만든 도형' 이라는 것입니다.

바로 이 두 부분을 이용해서 '부분 문제'를 이용하여 문제를 풀 수 있기 때문입니다.

'세로로 단조'라는 부분을 생각해봅시다. 

만약 아래쪽이 세로로 단조라면, 그 아래쪽을 제외한 위쪽이 세로로 단조이기만 하다면, 전체 도형은 세로로 단조인 것이 됩니다! 

그리고, 폴리오미노의 성질인 '정사각형들의 변들을 서로 완전하게 붙여 만든 도형'이라는 부분 덕분에, 

아래쪽 블록의 개수를 정해준다면, 나머지 블록으로 만드는 부분 문제의 폴리오미노 아래쪽 블록의 개수를 이용해서

폴리오미노를 몇 개 만들 수 있는지 구할 수 있습니다!

특히, 세로로 단조이기 때문에 맨 아래의 블록들 사이에는 빈 공간이 있어선 안됩니다.

이는 연속된 블록의 연결만이 맨 아래쪽 블록의 상태가 될 수 있다는 것입니다.

8개의 블록을 만드는 경우를 그림을 통해 확인해봅시다.

8개의 블록을 이용해 맨 아래의 블록을 4개로 정하고, 나머지 4개로 블록을 만드는 경우를 봅시다.

그렇다면 4개의 블록을 이용해 폴리오미노를 만드는 문제는 또 다시 아래 블록이 1개 이고, 나머지 3개의 블록으로 세로로 단조인 폴리오미노를 만드는 부분 문제로 나눌 수 있습니다.

그리고 4개의 블록과 1개의 블록을 통해서 4 가지의 서로 다른 폴리오미노를 만들 수 있습니다. 아래 그림을 통해 확인해 봅시다.

그렇다면 맨 아래의 블록 M이 주어지고, 그 다음 부분 문제에서 또다시 맨 아래의 블록 N이 주어진다면, 만들어 질 수 있는 개수는 몇 개일까요?

위 그림에서 보면, 맨 왼쪽의 블럭이 이동하는 횟수는 N + M - 1번 입니다. 겹치는 부분이 반드시 1칸 존재해야하기 때문에, 1을 빼주는 것입니다.

그렇다면, 이제 점화식을 세울 수 있습니다!

만들고자 하는 세로로 단조인 폴리오미노 개수를 n, 그리고 밑의 블록의 개수를 down이라고 한다면,

식은 아래와 같을 것 입니다.

메모이제이션에는 주어진 폴리오미노 블록 개수, 그리고 밑면의 개수를 이용한 이차원 배열을 만들면 됩니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
int poly[101][101] = { 0 };
const int MOD = 10000000;
 
int getPOLY(int nums, int down)
{
    int& ret = poly[nums][down];
 
    if (nums == down)
    {
        return ret = 1;
    }
 
    if (ret != -1) return ret;
 
    ret = 0;
 
    int blocks = nums - down;
    for (int i = 1; i <= blocks; i++)
    {
        ret += (i + down - 1) * getPOLY(blocks, i);
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        int n;
        scanf("%d\n", &n);
 
        memset(poly, -1, sizeof(poly));
 
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            res += getPOLY(n, i);
            res %= MOD;
        }
 
        printf("%d\n", res);
    }
 
    return 0;
}

여담

위 문제도 수가 매우 커질 수 있으므로 MOD를 통해 모듈라 연산을 한 점에 유의하도록 합시다!

생각보다 세로로 단조라는 점에서 부분 문제를 생각하는 것에서 시간을 꽤 소모했습니다.

풀고 나서 보면 굉장히 쉽고 직관적으로 찾을 수 있는 부분이었습니다!

이게 약간 동적 계획법의 매력이기도 한 부분입니다.

점화식이 쉽게 풀린다면 문제가 쉽게 풀립니다.

그래서 점화식을 풀고 문제가 정답이 된다면 큰 성취감을 얻을 수 있습니다.

물론, 부분 문제가 안보이면 시도하기 조차 힘들다는 단점도 있습니다..