백준 11727번 2*n 타일링 2

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

http://jaimemin.tistory.com/323와 비슷한 문제였습니다.

2*2 타일이 추가되었으므로 밑변의 길이가 2인 경우를 2배하는 것이 핵심이였습니다.

/*

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 10007;

 

int N;

int cache[1001];

 

//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) * 2 + tiling(width - 1)) % MOD;

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N>1000)

               exit(-1);

 

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

        cout << tiling(N) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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