BOJ 11726 - 2×n 타일링

문제 링크

문제#

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력#

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

출력#

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

풀이#

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

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

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

코드#

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

복잡도#

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

마무리#

바로 앞 두 경우만 이어 붙이면 2×n 타일링의 점화식이 자연스럽게 완성된다.