백준 11727번: 2 x n 타일링 2

[문제 링크]

11727번: 2×n 타일링 2

---

1x2, 2x1 타일을 사용해서 2 x n 직사각형을 채우는 문제의 업그레이드 버젼이다.

 

먼저, 1x2, 2x1 타일을 사용하는 타일링 문제의 점화식이 dp(n) = dp(n-1) + dp(n-2) 라는 것을 기억하자.

 

위 점화식에서 dp(n-1)은 2x(n-1) 타일을 채우는 방법의 수 * 2x1 타일을 채우는 방법의 수를 나타내는데,

2 x 1 타일을 채우는 방법이 한가지밖에 존재하지 않기 때문에 *1 이 생략된 것이다.

 

dp(n-2) 도 마찬가지로 2x(n-2) 타일을 채우는 방법의 수 * 2x2 타일을 채우는 방법의 수를 나타내는데,

2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법과 2x1 타일 2개로 채우는 방법이 존재하지만

2x1 타일 2개로 채우는 방법은 dp(n-1)과 중복되므로 제외시킨다.

따라서 2x2 타일을 채우는 방법도 한가지 밖에 존재하지 않기 때문에 *1이 생략된 것이다.

 

이 문제는 1x2, 2x1 타일과 추가로 2x2 타일을 사용할 수 있다고 한다.

2x2 타일이 추가되었기 때문에 2x1 타일을 채우는 방법의 수는 변함이 없다.

하지만 2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법에 추가로 2x2 타일 1개로 채우는 방법이 생기게 되므로 총 두가지 방법이 존재하게 되어 * 2를 해주어야 한다.

 

따라서 이 문제의 점화식은 다음과 같다.

dp(n) = dp(n-1) + (dp(n-2) * 2)

 

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

const int MOD = 10007;
int memo[1001];

int Topdown(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 3;

	int& ret = memo[n];
	if (ret != 0) return ret;

	return ret = (Topdown(n - 1) + (Topdown(n - 2) * 2)) % MOD;
}

int Bottomup(int n)
{
	memo[1] = 1;
	memo[2] = 3;

	for (int i = 3; i <= n; i++)
		memo[i] = (memo[i - 1] + (memo[i - 2] * 2)) % MOD;

	return memo[n];
}

int main(void)
{
	int n;
	cin >> n;
	
	// Top-down
	cout << "Top-down: " << Topdown(n) << endl;
	
	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 66 day