algospot ASYMTILING

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

기존에 타일링 문제를 풀어봤으면 비교적 쉽게 풀 수 있을 것 같습니다.

/*

TILING2와 같이 2*n 크기의 직사각형을

2*1 크기의 타일로 채우려고 한다.

하지만 이 때 대칭을 이루지 않는 경우의 수만 구하시오

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 1000000007; //32bit로 표현할 수 있는 수 넘었을 경우 대비

int cache[101];

//int cache2[101]; //직접세는 경우 고려

//2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환

int tiling(int width)

{

        //기저 사례:width가 1 이하일 때

        if (width <= 1)

               return 1;

        //메모이제이션

        int &result = cache[width];

        if (result != -1)

               return result;

        //가로로 두개를 끼워놓는 경우 혹은 세로로 1개를 끼워놓는 경우

        return result = (tiling(width - 2) + tiling(width - 1)) % MOD;

}

 

//비대칭인 경우

//2*width 크기의 사각형을 채우는 비대칭 방법의 수 반환

int asymmetric(int width)

{

        if (width % 2 == 1) //가로의 길이가 홀수

               return (tiling(width) - tiling(width / 2) + MOD) % MOD; //가운데 2*1 직사각형 하나를 기준으로 대칭인 경우 뺀다

        int result = tiling(width);

        //반면 가로의 길이가 짝수 일경우에는 가운데 1*2 직사각형 두개를 기준으로 대칭인 경우(1)와

        //반으로 갈랐을 때 양 옆이 대칭인 경우(2)를 고려해야한다.

        //즉 두가지 경우를 고려해야하기 때문에 식이 두개

        result = (result - tiling(width / 2) + MOD) % MOD; //(2)

        result = (result - tiling(width / 2 - 1) + MOD) % MOD; //(1)

        return result;

}

 

/*

//직접 비대칭 타일링의 수를 세는 동적 계획법 알고리즘

//총 4가지의 경우의 수가 있음

//(1) 양쪽에 2*1 직사각형을 놓을 경우(남은 칸 대칭이면 안됨)

//(2) 양쪽에 1*2 직사각형을 놓을 경우(남은 칸 대칭이면 안됨)

//(3) 왼쪽 끝에는 2*1 직사각형 오른쪽 끝에는 1*2 직사각형(남은 칸 대칭이여도 됨)

//(4) 왼쪽 끝에는 1*2 직사각형 오른쪽 끝에는 2*1 직사각형(남은 칸 대칭이여도 됨)

int countAssymmetric(int width)

{

        //기저 사례:너비가 2이하인 경우

        if (width <= 2)

               return 0;

        //메모이제이션

        int &result = cache2[width];

        if (result != -1)

               return result;

        result = countAssymmetric(width - 2) % MOD; //(1)

        result += countAssymmetric(width - 4) % MOD; //(2)

        result += tiling(width - 3) % MOD; //(3)

        result += tiling(width - 3) % MOD; //(4)

        return result;

}

*/

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case > 50 || test_case < 1)

               exit(-1);

 

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

        {

               int width;

               cin >> width;

               if (width < 1 || width>100)

                       exit(-1);

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

               cout << asymmetric(width) << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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

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