백준 11727번 문제 : 2xn 타일링 2

문제 링크 : 백준 11727번 : 2xn 타일링 2

이 문제는 11726번을 조금 응용한 문제이다. n을 입력받아 2xn 크기의 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제이다. 앞서 11726 문제 풀이에서 d[n]은 d[n-2]의 직사각형의 오른쪽에 누운 직사각형 2개를 붙인 경우의 수와, d[n-1]의 직사각형의 오른쪽에 세운 직사각형 1개를 붙인 경우의 수를 합치면 되었다. 이번에도 간단하다. d[n-2]의 오른쪽에 붙일 누운 직사각형 2개를, 2x2의 타일로 대체해서 똑같이 더해주면 된다. 결과적으로 각 경우마다 한 가지의 경우씩 더 생기는 것이므로 2를 곱해주면 해결된다.

#include <iostream>
using namespace std;

int main()
{
	int n;
	int d[1001];
	cin >> n;
	d[0] = 1; d[1] = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = (d[i - 1] + (d[i - 2] * 2)) % 10007;
	}
	cout << d[n];
	
    return 0;
}