[Week 5] ASYMTILING self review - Scaachan

[Queue-ri]

ASYMTILING self review

• 파일명: ASYMTILING/Scaachan.cpp
• 수행시간: 4ms

1. 문제 해결 과정

전체 - 대칭되는 경우의 수 로 접근하면 된다고 생각했습니다.

경우의 수를 뺄 때는, 빼는 쪽의 값이 더 클 때를 고려해서 무조건 10^9+7을 한 번 더한 뒤 모듈러 연산을 해줍니다.

2. 아이디어

1. TILING2 문제에서 작성했던 함수처럼 0~N까지 모든 타일링 방법의 수를 구하는 함수를 작성합니다.
2. N이 홀수일 때: 정 가운데 1 * 2(가로 * 세로) 타일은 고정된 채 양쪽만 패턴이 같으면 대칭이므로, 1에서 구한 값에 N/2 까지의 타일링 방법의 수를 뺍니다.
3. N이 짝수일 때: 1에서 구한 값 - (고정 타일 없이 N/2 까지의 타일링 방법의 수 + 가운데 두 개의 2 * 1 타일이 고정된 N/2-1 까지의 타일링 방법의 수)

3. 코드 설명

ll memo[101];

ll tiling(int N) {
	if (N == 1 || N == 2) return N;
	ll& cache = memo[N];
	if (cache) return cache;

	return cache = (tiling(N - 1) + tiling(N - 2)) % P;
}

타일링하는 재귀함수를 TILING2 문제에서 조금 변형했습니다.

이번 문제는 tiling() 함수에서 N 말고도 N/2, N/2-1 가 base case로 쓰이기 때문에

0~N이 아닌 N~0의 역순으로 내려가는 함수를 작성하는 것이 가독성에 더 좋았습니다.

	if (N == 1 || N == 2)
		cout << 0 << endl;
	else if (N & 1)
		cout << (tiling(N) - tiling(N>>1) + P) % P << endl;
	else {
		ll ans = tiling(N);
		ans = (ans - tiling(N>>1) + P) % P;
		ans = (ans - tiling((N>>1)-1) + P) % P;
		cout << ans << endl;

1. 문제 해결 과정 에서 설명한 것을 그대로 구현한 코드입니다.

다만 N이 1 또는 2일 때는 구현한 로직이 적용되지 않는 corner case 이므로 따로 처리해줍니다.