algospot POLY

문제링크입니다: https://algospot.com/judge/problem/read/POLY

솔직히 손도 대지 못한 문제였습니다.

'폴리오미노'라는 개념을 처음 알았고 '세로로 단조'라는 표현도 처음 알았기 때문입니다.

책의 풀이는 정말 끝내줍니다. 최근 푼 문제들처럼 동적 계획법을 사용하여 푸는데 첫번째 줄에 몇개의 블록을 사용할 것인지를 토대로 답을 구해내는 풀이였습니다.

풀이를 보면서 '아직 갈 길이 멀구나'라는 생각이 들면서도 흥미로워하는 것을 보면 프로그래밍이 적성에 맞는 편인 것 같습니다!

/*

정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노라고 한다

n개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데,

이 중 세로로 단조인 폴리오미노의 수가 몇개나 되는가?

 

세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두번 이상 교차하지 않는다는 뜻이다.

ex)

2개의 정사각형일 경우(2가지)

ㅁ ㅇㅇ

ㅁ

4개의 정사각형일 경우(19가지)

ㅁ ㅇㅇ ㅁㅁ ㅇ     ㅁ ㅇ     ㅁ

ㅁ   ㅇ ㅁ   ㅇㅇ ㅁㅁ ㅇㅇ ㅁㅁ

ㅁ   ㅇ ㅁ     ㅇ   ㅁ ㅇ   ㅁ

ㅁ

                      ㅇ     ㅁ  

ㅁㅁㅁ ㅇㅇㅇ ㅁㅁㅁ  ㅇ     ㅁ 

    ㅁ   ㅇ   ㅁ      ㅇㅇ ㅁㅁ

 

ㅇㅇ   ㅁㅁ   ㅇㅇ ㅁ       ㅇ

  ㅇㅇ ㅁㅁ ㅇㅇ   ㅁㅁㅁ ㅇㅇㅇ

   

        ㅇ ㅁㅁㅁㅁ

ㅇㅇㅇ

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 10000000; //1,000,000을 넘어갈 경우 적절한 크기의 답을 구하기 위한 modulation

int cache[101][101]; //최대 100이고 0번째 index를 사용하지 않으므로

 

//n개의 정사각형으로 이루어졌고, 맨 위 가로줄에 first개의

//정사각형을 포함하는 폴리오미노의 수를 반환

int poly(int n, int first)

{

        //기저 사례:n==first

        if (n == first)

               return 1;

        //메모이제이션

        int &result = cache[n][first];

        if(result!=-1)

               return result;

        result = 0;

        //맨 위 가로줄에서부터 second번째 밑에 있는 층의 블록 수

        //poly(n, first)=∑(second+first-1) * poly(n-first, second);

        for (int second = 1; second <= n - first; second++)

        {

               //맨 윗줄에 first개의 정사각형이 있고, 나머지 사각형으로 만든 폴리오미노의 첫 줄에 second개의

               //정사각형이 있다고 했을 때  이들을 붙일 수 있는 방법의 수는 first+second-1

               //ex) first 2 second 2(2+2-1=3가지)

               //  ㅁㅁ ㅁㅁ ㅁㅁ

               //ㅁㅁ   ㅁㅁ   ㅁㅁ

               //ex) first 2 second 3(2+3-1=4가지)

               //  ㅁㅁ     ㅁㅁ ㅁㅁ   ㅁㅁ

               //ㅁㅁㅁ ㅁㅁㅁ   ㅁㅁㅁ   ㅁㅁㅁ

               int add = second + first - 1;

               add *= poly(n - first, second); //n-first개의 정사각형 중 해당 층에는 second개 사용

               add %= MOD;

               result += add;

               result %= MOD;

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               int block, sum = 0;

               cin >> block;

               if (block < 1 || block>100)

                       exit(-1);

               memset(cache, -1, sizeof(cache));

               for (int j = 1; j <= block; j++)

               {

                       sum += poly(block, j);

                       sum %= MOD;

               }

               cout << sum << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략