백준 2133번 타일 채우기

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

타일링 문제가 상당히 흥미로웠기 때문에 백준 알고리즘 문제를 한번 풀어봤습니다.

알고스팟에서 익혔던 방법대로 풀었더니 쉽게 풀렸습니다! (http://jaimemin.tistory.com/323?category=985009)

주석으로 설명도 작성하였으니 이해가 쉽게 될 것이라고 생각합니다.

/*

3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하시오

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int cache[31]; //최대 30

 

//이 문제는 그림을 그렸을 때 잘 풀린다(아래와 같은 형태로 풀면 쉽게 풀린다)

//■■는 1*2, ㅁ는 2*1 직사각형

//            ㅁ

/*

3*2의 경우 = 3가지

■■ ㅁㅁ ■■

ㅁㅁ ㅁㅁ ■■

ㅁㅁ ■■ ■■

*/

/*

3*4의 경우 = 11가지

(3*2의 경우)*(3*2의 경우) = 9가지

         +

3*4의 고유 모양 = 2가지

■■■■ ㅁ■■ㅁ

ㅁ■■ㅁ ㅁ■■ㅁ

ㅁ■■ㅁ ■■■■

*/

/*

3*6의 경우 = 41가지

(3*2의 경우)*(3*4의 경우) = 33가지

            +

(3*4의 고유 모양)*(3*2의 경우) = 6가지

                       +

3*6의 고유 모양 = 2가지

■■■■■■ ㅁ■■■■ㅁ

ㅁ■■■■ㅁ ㅁ■■■■ㅁ

ㅁ■■■■ㅁ ■■■■■■

*/

/*

3*8의 경우 = 153가지

(3*2의 경우)*(3*6의 경우) = 123가지

              +

(3*4의 고유 모양)*(3*4의 경우) = 22가지

              +

(3*6의 고유 모양)*(3*2의 경우) = 6가지

              +

3*8의 고유 모양= 2가지

■■■■■■■■ ㅁ■■■■■■ㅁ

ㅁ■■■■■■ㅁ ㅁ■■■■■■ㅁ

ㅁ■■■■■■ㅁ ■■■■■■■■

*/

 

int tiling(int width)

{

        //기저 사례:width가 홀수일 때 성립 X

        if (width % 2 == 1)

               return 0;

        else if (width == 0) //기본 값(width가 2일 때를 고려하여)

               return 1;

        else if (width == 2) //3*2의 직사각형을 채우는 경우의 수는 3가지다

               return 3;

        //메모이제이션

        int &result = cache[width];

        if (result != -1)

               return result;

        result = 3 * tiling(width - 2); //tiling(2) * tiling(width-2)

        for (int i = 0; i <= width - 4; i++) //width-4부터는 고유 모양을 더해나가야하므로

               result += 2 * tiling(i); //고유모양 2가지 * tiling(i)

        return result;

}

 

int main(void)

{

        int width;

        cin >> width;

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

        cout << tiling(width) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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