[Week 5] ASYMTILING self review - hanjuuuuuu

[hanjuuuuuu]

ASYMTILING self review

1. 해결 시도 과정

비대칭보다 수가 적기 때문에, 대칭인 모든 경우를 그려보며 확인하고, 특징을 찾으려고 했습니다. n(width)이 홀수일 경우와 짝수일경우를 나눠서 특징을 찾았고, 전체 타일링방법에서 대칭타일링을 빼서 비대칭타일링 방법 수를 얻게 했습니다. 홀수일 경우는 가운데가 세로 직사각형이고, 그것을 기준으로 왼쪽과 오른쪽이 대칭이어야 합니다. 짝수일 경우는 가운데로 접히거나, 가운데에 가로 직사각형이 2개 위치하고, 이것을 기준으로 대칭이어야합니다.

2. 아이디어

전체 타일링방법 수는 피보나치 수열의 형태를 띄고 있습니다. 완전탐색한 뒤, 메모이제이션을 사용해 저장하였습니다. MOD로 나눴을 때, 음수가 나올 수 있으므로 +MOD 한 후에 % MOD를 해야합니다.

3. 코드 설명

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
int cache[101];		//전체 타일링 개수

int tiling(int width) {		//타일링 개수 세기
	if (width <= 1)
		return 1;
	//메모이제이션
	int& ret = cache[width];
	if (ret != -1)
		return ret;
	return (tiling(width - 2) + tiling(width - 1)) % MOD;	//가로로 2개, 세로로 1개인 경우
}

int asymtiling(int width) {		//비대칭 타일링 수 구하기
	int ret = tiling(width);
	if (width % 2 == 1) //width가 홀수일 경우
		return (tiling(width) - tiling(width / 2) + MOD) % MOD;
	else {	//width가 짝수일 경우
		ret = (ret - tiling(width / 2) + MOD) % MOD;	//전체- 가운데 기준으로 양옆이 대칭인 경우
		ret = (ret - tiling(width / 2 - 1) + MOD) % MOD;	//전체 - 가운데 가로2개 기준으로 대칭인 경우
		return ret;
	}
}

int main() {
	int C;
	cin >> C;
	while (C--) {
		int N;
		cin >> N;
		memset(cache, -1, sizeof(cache));
		cout << asymtiling(N) << endl;
	}
	return 0;
}

4. 막힌 점 및 개선 사항

시간초과가 나왔는데, 조금 더 수정해서 시간을 줄여야 할 것 같습니다.