01타일 (feat. 백준, 1904번)

01타일
https://www.acmicpc.net/problem/1904

1904번: 01타일

반응형

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

1. A(1) = 1, A(2) = 2, A(3) = 3, A(4) = 5, A(5) = 8 의 결과를 얻을 수 있습니다. 즉, 0은 00 으로 시작되고, 1은 1로 시작됩니다.
2. 따라서 A(N) = A(N-1) + A(N-2) (단, N >= 3일때) 의 수식을 도출할 수 있습니다.