백준 11726 : 2×n 타일링 - C++

어제 소개해드렸던 9095번 : 1, 2, 3 더하기와 비슷한 문제입니다.

경우의 수들을 나열해서 적어보고 적절한 점화식을 찾아봅시다!

 

편의상

가로 길이가 1인 타일을 하나 배치하는 경우를 1로,

가로 길이가 2인 타일을 위 아래 두 개 배치하는 경우를 2로,

명칭하도록 하겠습니다.

 

2x1 직사각형에 타일을 채우는 경우 : 1

2x2 직사각형에 타일을 채우는 경우 : 1, 1 / 2

2x3 직사각형에 타일을 채우는 경우 : 1, 2 / 1, 1, 1 / 2, 1

2x4 직사각형에 타일을 채우는 경우 : 1, 1, 2 / 2, 2 / 1, 2, 1 / 1, 1, 1, 1 / 2, 1, 1

힌트가 보이시나요?
2x3의 경우, 2x1 경우의 오른쪽에 2를 더한 것과 2x2 경우의 오른쪽에 1을 더한 것을 합친 경우이고,

2x4의 경우, 2x2 경우의 오른쪽에 2를 더한 것과 2x3 경우의 오른쪽에 1을 더한 것을 합친 경우와 같습니다.

 

즉, A(n)이 2xn 직사각형에 타일을 채우는 경우의 수라고 했을 때,

$$ A(n) = A(n-1) + A(n-2) $$

입니다.

 

위 점화식을 사용해서 문제를 해결할 수 있습니다.

 

#include <iostream>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	if (n <= 3) {
		cout << n;
		return 0;
	}

	int pres;
	int res = 3;
	int prev = 2;
	for (int i = 4; i <= n; ++i) {
		pres = res;
		res = res + prev;
		if (res >= 10007) res = res % 10007;
		prev = pres;
	}

	cout << res;

	return 0;
}