BOJ 11727 - 2×n 타일링 2

문제 링크

문제#

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력#

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력#

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이#

끝부분에 어떤 타일이 놓이는지만 생각하면 점화식이 자연스럽게 나온다. 마지막 한 칸이나 두 칸을 어떻게 채웠는지로 경우를 나누면 이전 상태의 답을 재사용할 수 있다.

코드에서는 작은 길이부터 차례대로 채워 가며 dp[n]을 만든다. 2×n 타일링 계열은 결국 마지막 모양만 분리하면 앞쪽은 다시 같은 문제로 돌아간다.

경우를 직접 나열하기보다, 마지막 배치가 무엇인지로만 나누는 것이 핵심이다. 그 순간 재귀적 구조가 바로 보인다.

코드#

#include <iostream>
using namespace std;
 
void solve() {
	int arr[1001] = {};
	arr[1] = 1;
 
	int n;
	cin >> n;
 
	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0)
			arr[i] = ((arr[i - 1] * 2) + 1) % 10007;
		else
			arr[i] = ((arr[i - 1] * 2) - 1) % 10007;
	}
 
	cout << arr[n] << '\n';
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: $1$부터 $N$까지 DP를 채우므로 $O(N)$이다.
• 공간 복잡도: DP 배열을 저장하므로 $O(N)$이다.

마무리#

2×2 타일이 하나 더 들어오면서 점화식 계수만 달라질 뿐, 구조는 같은 DP다.