algospot TILING2

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

동적계획법을 사용한다면 간다하게 풀 수 있었던 문제였습니다.

/*

2*n 크기의 사각형을 2*1 크기의 타일로 채우는 방법의 수를 계산하시오

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

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

int cache[100];

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

int tiling(int width)

{

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

        if (width <= 0)

               return 1;

        //메모이제이션

        int &result = cache[width];

        if (result != -1)

               return result;

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

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

}

 

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 << tiling(width-1) << endl << endl; //cache의 크기가 100이므로 width-1

        }

        return 0;

}

개발환경:Visual Studio 2017

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

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