2×n 타일링 2 (feat. 백준, 11727번)

2×n 타일링 2
https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

반응형

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

1. 손으로 4개까지는 구할수가 있었는데요. 1 = 1, 2 = 3, 3 = 5, 4 = 11 이었습니다.
2. 여기서 현재의 N을 Ai라고 하면, Ai = Ai-2 * 2 + Ai-1 이라는 식이 도출됩니다. (단, N은 3 이상인 경우)