알고리즘 문제해결 전략 Chapter 08 - TILING2(C++)

예제: 타일링 방법의 수 세기

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.

예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. (알고스팟 홈페이지에 그림이 없어서, 임의로 3개만 그렸다. 8개 그리기는 귀찮았다!!)

경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

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

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

예제 입력

3
1
5
100

예제 출력

1
8
782204094

풀이

근래 풀었던 문제중에 맘편히 풀었던 것 같다.

2차원 문제같지만, 어차피 2칸 앞으로 가거나 1칸 앞으로 가기 때문에 1차원 문제이다.
이 점만 고려해줘서 현재 위치에서 사각형을 채우는 개수를 세는 재귀함수를 만들었다.

다만, 주의해야 할 점은 mod 연산이 있다는 것이다. 적절한 위치에 mod연산을 해 주지 않으면 잘 풀어놓고도 틀릴 수 있다.

예를 들어,

    for (int i = 1; i <= 2; i++) {
        res += tiling(idx + i);
        res %= MOD;
    }

이 코드의 결과와

    for (int i = 1; i <= 2; i++) {
        res += (tiling(idx + i) % MOD);
    }

이 코드의 결과는 분명히 다르다. 함수의 결과가 tiling(idx + i) = 2이고, MOD가 3이라고 생각해보면 금방 답이 나올 것이다. 필자가 틀려봐서 안다. 촤핫😅

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<cstring>

using namespace std;

const int MOD = 1000000007;
int n;
int cache[100];

int tiling(int idx) {
	//기저사례: 사각형 끝에 닿았을 때 성공
	if (idx >= n - 1) return 1;

	int& res = cache[idx];
	if (res != -1) return res;

	res = 0;
	for (int i = 1; i <= 2; i++) {
		res += tiling(idx + i);
		res %= MOD;
	}

	return res;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		memset(cache, -1, sizeof(cache));
		cin >> n;

		cout << tiling(0) << endl;
	}

	return 0;
}

풀이 후기

이 문제는 전에도 풀었었는데, 지금 다시 풀어보니 풀이법이 상당히 다르다.
지금은 사각형을 채워가는 식이었다면, 저번에는 사각형을 빼는 방식으로 풀었다.
같은 사람이라도 이렇게 풀이방법이 다른데 다른 사람들끼리는 오죽 할까.
최선의 알고리즘도 수많은 알고리즘들이 나온 덕택에 점점 발전해가는것이 아닐까 싶다.