2xn 타일링 (feat. 백준, 11726번)

2xn 타일링
https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11726
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int n, arr[1001] = { 0 };
	arr[1] = 1, arr[2] = 2;
	cin >> n;
	for (register int i = 3; i <= n; ++i)
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	cout << arr[n] << endl;
	return 0;
}
// *&)*@*

1. n이 1일때는 2x1 하나만 설치할 수 있습니다.
2. n이 2일때는 1x2 두개 또는 2x1 두개를 설치할 수 있습니다.
3. n이 3일때는 1x2 두개 + 2x1 한개 / 2x1 한개 + 1x2 두개 / 2x1 세개 로 설치할 수 있습니다.
4. 따라서 Ai = Ai-1 + Ai-2 의 식을 도출할 수 있습니다.
5. 입력값의 max인 1000을 입력하면 integer 범위를 넘는 것을 알 수 있고, 따라서 수식을 구하는 반복문 내에서 10007의 나머지를 미리 구하여 대입합니다.

​