백준 2718번 타일 채우기

문제 링크입니다: https://www.acmicpc.net/problem/2718

백준 2133번 타일 채우기(http://jaimemin.tistory.com/330)는 높이가 3인 직사각형이였는데 이번 문제는 높이가 4인 직사각형에 타일을 채우는 문제였습니다.

이런 문제는 직접 경우의 수를 그려봐야 경우의 수를 구할 수 있고, 한칸 전 즉, width - 1에서 타일을 채운 방법을 알아야지 경우의 수를 구할 수 있습니다.

주석에도 각 경우의 그림을 표현하였고 자세한 설명은 http://joonas-yoon.blogspot.com/2016/03/2718.html을 참고하시면 될 것 같습니다!

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

 

/*

0 1 2 3

o o o x

o o x o

o x x o

o x o x

*/

/*

0 1

x x

x x

x o

x o 도 가능

*/

int cache[MAX][4];

 

int tiling(int width, int state)

{

        if (width == 0)

                 return !state;

       

        int &result = cache[width][state];

        if (result != -1)

                 return result;

 

        switch (state)

        {

        /*

        xo xx xo xx xx

        xo xx xo xx xo

        xo xx xx xo xo

        xo xx xx xo xx

        */

        case 0:

                 result = tiling(width - 1, 0) + tiling(width - 2, 0) + tiling(width - 1, 1) * 2 + tiling(width - 1, 3);

                 break;

        /*

        xo xx

        xo xx

        xo xo

        xo xo

        */

        case 1:

                 result = tiling(width - 1, 0) + tiling(width - 1, 1);

                 break;

        /*

        xx

        xo

        xo

        xx

        */

        case 2:

                 result = tiling(width - 1, 3);

                 break;

        /*

        xo xo

        xo xx

        xo xx

        xo xo

        */

        case 3:

                 result = tiling(width - 1, 0) + tiling(width - 1, 2);

                 break;

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

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

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

        {

                 int N;

                 cin >> N;

                 cout << tiling(N, 0) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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