동적 계획법 - 11. 비대칭 타일링

문제 : 비대칭 타일링 (난이도 : 下)

 

https://www.algospot.com/judge/problem/read/ASYMTILING

 

 분석

위 문제는 이 문제의 연장선이다.

2021/01/01 - [알고리즘 문제 해결 전략] - 동적 계획법 - 8. 타일링 방법의 수 세기

동적 계획법 - 8. 타일링 방법의 수 세기

이 문제는 두 가지 방법으로 풀 수 있는데 어느 것을 선택하느냐에 따라 난도가 살짝 달라진다.

첫 번째 방법은 전체 경우의 수에서 대칭인 경우를 빼는 것이다.

두 번째 방법은 비대칭인 경우의 수를 직접 구하는 것이다.

난도는 첫 번째 방법이 쉬우나 공부하는 과정이기에 둘 다 서술하고자 한다.

 

첫 번째 방법은 width가 홀수이냐 짝수이냐에 따라 대칭을 판단하는 여부가 달라진다.

 

대칭인 경우

대칭적인 구조이기 때문에 한쪽에서의 경우의 수를 구해 전체 경우의 수에서 빼주면 쉽게 답을 구할 수 있다.

 

두 번째 방법은 다음과 같은 구조들을 배합해가면 된다.

 

a, b인경우 대칭이기에 재귀 호출을 통해 해결하고 c, d인 경우 비대칭이므로 파란색 부분을 덮는 전체 경우의 수를 반환하면 된다.

코드와 함께 보면 어떤 말인지 이해가 될 것이다.

 

 구현

int MOD = 1000000007;
int cache[101];
//2xWidth 크기의 사각형을 채우는 경우의 수를 반환한다.
int tiling(int width)
{
	//base case : 마지막 칸인 경우
	if (width <= 1) return 1;
	//memoization
	int& ret = cache[width];
	if (ret != -1) return ret;
	return ret = (tiling(width - 1) + tiling(width - 2)) % MOD;
}

//2xWidth 크기의 사각형을 채우는 비대칭 방법의 수를 반환한다.
//전체 경우의 수 - 대칭인 경우의 수
//MOD를 더하는 이유는 경우의 수는 양수이기때문이다.
int asymmetric(int width)
{
	//width가 odd인경우
	if (width % 2 == 1)
	{
		return (tiling(width) - tiling(width / 2) + MOD) % MOD;
	}
	int ret = tiling(width);
	ret = (ret - tiling(width / 2) + MOD) % MOD;
	ret = (ret - tiling(width / 2 - 1) + MOD) % MOD;
	return ret;
}

int cache2[101];
//비대칭인 경우의 수를 반환한다.
int asymmetric2(int width)
{
	//base case : 너비가 2이하인 경우
	if (width <= 2) return 0;
	//memoization
	int& ret = cache2[width];
	if (ret != -1) return ret;
	ret = asymmetric2(width - 2) % MOD; //a 
	ret = (ret + asymmetric2(width - 4)) % MOD; //b
	ret = (ret + tiling(width - 3)) % MOD; //c
	ret = (ret + tiling(width - 3)) % MOD; //d
	return ret;
}


int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		memset(cache2, -1, sizeof(cache));
		int n;
		cin >> n;
		cout << "1번째 방법 : " << asymmetric(n) << '\n';
		cout << "2번째 방법 : " << asymmetric2(n) << '\n';
	}
	return 0;
}