알고리즘 스터디/dynamic programming

비대칭 타일링

ddongyeonn 2020. 3. 9. 13:58

문제

2xn 크기의 직사각형을 2x1크기의  타일로 채우려고 한다. 타일은 겹쳐서는 안 되고, 90도로 회전하여 사용이 가능하며 결과가 좌우 대칭이어서는 안 된다. n이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 결과값은 1,000,000,007로 나눈 나머지를 출력합니다.

입력

첫 줄에는 테스트 케이스의 수 C(1~50)가 주어짐

다음 줄부터 사각형 너비 N(1~100)이 주어짐

예제 입력 및 출력

입력

3

2

4

92

 

출력

0

2

913227494

소스코드

#include <iostream>
#include <vector>

using namespace std;

int Case;
int cache1[101]; //넓이가 width인 직사각형을 무작위로 채우는 경우의 수 저장
int cache2[101]; //넓이가 width인 직사각형을 대칭이 아니게 채우는 경우의 수 저장
const int mod = 1000000007;

class tile {
private:
	int recwidth;
public:
	void Input() {
		cin >> recwidth;
	}
	int getwidth() {
		return recwidth;
	}
	//타일을 무작위로 채우는 경우의 수 구하는 함수
	int tiling(int width) {

		//타일을 다 채웠다면 1반환
		if (width <= 1)
			return 1;
		
		//cache값 있으면 반환(현재 넓이의 사각형을 채우는 경우의 수는 이미 계산되었다)
		if (cache1[width] != -1)
			return cache1[width];
		
		//현재 넓이의 사각형 채우는 경우의 수 계산
		cache1[width] = (tiling(width - 1) + tiling(width - 2)) % mod;
		return cache1[width];
	}
	//타일을 대칭이 아니도록 채우는 경우의 수 구하는 함수
	int symmetry(int width) {

		//타일이 2칸 이하로 남으면 0반환
		if (width <= 2)
			return 0;

		//cache값 있으면 반환
		if (cache2[width] != -1)
			return cache2[width];

		cache2[width] = (symmetry(width - 2)) % mod; //양쪽 2x1 타일을 붙인 경우
		cache2[width] = (cache2[width] + symmetry(width - 4)) % mod; //양쪽 2x2 타일을 붙인 경우
		//양쪽에 2x1 2x2 / 2x2 2x1타일을 붙인 경우 ->바로 모든 경우의 수
		cache2[width] = (cache2[width] + tiling(width - 3)) % mod;
		cache2[width] = (cache2[width] + tiling(width - 3)) % mod;
		return cache2[width];
	}
};

tile* mytile;

int main(void) {
	cin >> Case;

	mytile = new tile[Case];

	for (int i = 0; i < Case; i++) {
		mytile[i].Input();
	}
	
	for (int i = 0; i < Case; i++) {
		memset(cache1, -1, sizeof(cache1));
		memset(cache2, -1, sizeof(cache2));
		cout << mytile[i].symmetry(mytile[i].getwidth()) << endl;
	}
	return 0;
}

문제 풀이

 1. 문제 해결 전략

  • 양쪽에 2x2타일을 붙이거나 2x1타일을 붙인 경우 -> 내부 타일을 어떻게 붙이는지에 따라 대칭이 될 수도 있고 비대칭이 될 수도 있다. -> 회색 부분 넓이를 인자로 전달하여 symmety함수를 재귀 호출한다.

대칭인지 비대칭인지 모름

  • 양쪽에 2x1, 2x2 타일을 하나씩 붙인 경우 -> 내부 타일 모양에 상관없이 무조건 비대칭 타일이 된다.  -> 회색 부분 넓이를 tiling함수에 전달하면 타일을 붙일 수 있는 모든 경우의 수를 알 수 있다.

 

 

 

무조건 비대칭 타일

 2. cache값 이용

  • cache1[width] = 넓이가 width인 사각형에 타일을 무작위로 배치해 채우는 경우의 수

  • cache2[width] = 넓이가 width인 사각형에 타일을 비대칭이 되도록 채우는 경우의 수

 3. 기저 사례

  • cache값이 이미 계산되었으면 바로 반환

 4. 함수 탈출 조건

  • tiling함수 탈출 조건 : width가 1인 경우 2x1사각형 채우고 1반환, width가 0인 경우 바로 1 반환

  • symmetry함수 탈출 조건 : width가 2 인경우 2x1사각형 2개를 채워야 하는데 그럼 전체가 대칭이 되므로 0 반환, width가 1 인 경우 사각형을 다 채울 수 없는 배치 방법으로 0을 반환, wid가 0인 경우 전체가 대칭인 경우이므로 0 반환

 5. 점화식

  • tiling 함수

    • cache1[width] = tiling(width-1) + tiling(width-2)

    • 현재 넓이의 사각형을 무작위로 타일링 하는 경우의 수는 2x1사각형 한 개를 채우고 width-1을 다시 타일링하는 경우의 수 + 2x2사각형을 채우고 width-2를 다시 타일링 하는 경우의 수

  • symmetry 함수

    • cache2[width] = symmetry(width-2) // 양쪽에 2x1사각형을 붙이고 width-2를 비대칭 타일링  

    • cache2[width] += symmetry(width-4) // 양쪽에 2x2사각형을 붙이고 width-4를 비대칭 타일링

    • cache2[width] += tiling(width-3) // 양쪽에 2x1 2x2 사각형을 붙이고 width-3을 무작위 타일링(2회 반복)