예제: 타일링 방법의 수 세기(ID:TILING2)

문제

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.
예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.
경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 경우의 수를 1000000007로 나눈 나머지를 출력합니다.

예제 입력

3
1
5
100

예제 출력

1
8
782204094

First Thoughts

타일의 배치 방법

21의 타일을 배치하는 방법은 2가지가 있다. 세로로 세우는 방법(|)과 가로로 2개를 눕히는 방법이 있다. 이 두 가지 방법으로 2n의 타일을 채우는 함수를 재귀적으로 작성하면 될 거 같다.

My Code

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int cache[101];
int sum(int n) {
	if (n <= 1)
		return 1;
	int& ret = cache[n];
	if (ret != -1)
		return ret;
	return ret = (sum(n - 1) + sum(n - 2))% 1000000007;
}
int main() {
	int C;
	int i;
	int n;
	cin >> C;
	for (i = 0; i < C; i++) {
		memset(cache, -1, sizeof(cache));
		cin >> n;
		cout << sum(n) << endl;
	}
}

Answer Code

#include <iostream>
#include <cstring>
#include <algorithm>
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 ret = (tiling(width - 1) + tiling(width - 2)) % MOD;
}
int main() {
	int C;
	int i, n;
	cin >> C;
	for (i = 0; i < C; i++) {
		memset(cache, -1, sizeof(cache));
		cin >> n;
		cout << tiling(n) << endl;
	}
}

Difference & Faults

width가 1보다 작을 때

나는 n이 항상 1보다 크거나 같을 거라고 확신을 갖고 if(n==1)을 기저사례로 두었다. 하지만 n을 뺄셈하는 과정에서 0이나 음수가 나올 수 있다는 것을 알게되었다. if(n<=1)로 고치니까 정답이 나왔다.

MOD의 사용

엄청 큰 수를 "MOD"라는 변수에 저장하여 이를 이용한 점이 새로웠다. "1000000007"이라는 수가 크고 복잡하여 한개로 실수하면 처음부 다시 세고 고쳐야한다. 이 문제의 경우 1000000007이라는 수를 결과 도출을 할때 마지막 한 번만 사용되지만 저런 복잡한 수가 여러번 사용될 때는 따로 변수에 저장하여 사용하면 실수를 방지할 수 있을 것이다.

Impressions

이 문제는 경우의 수를 계산하는 문제로서 재귀적인 특징을 가지고 있다. 책에서는 타일링할 수 있는 2가지 기법에 대해 이렇게 설명하고 있다. "두 가지 분류는 타일리하는 방법을 모두 포함한다", "두 가지 분류에 모두 포함되는 타일링 방법은 없다". 즉 각각의 방법은 유일무이해야한다는 것이다. 다른 경우의 수를 계산하는 문제를 접할 때도 분류할 수 있는 방법이 독립적이어야함을 유의하자.

Summary

타일의 배치방법을 통해 메모제이션을 구현하는 것까지 어려운 과정은 아니었다. 그래서 정말 미세한 부분말고는 코드가 매우 유사하다. 물론 난이도가 높은 문제는 아니었지만 해답 코드와 비슷하게 구현하여 기분이 좋다.