시뮬레이션으로 직접 경우의 수를 세면 시간 복잡도가 n번째 피보나치 수가 되기 때문에 다이나믹 프로그래밍을 이용해야 하는 문제이다. i번째에 어떻게 도달했는지를 생각하여 i-1번째에서 1타일을 설치한 경우+i-2번째에서 00타일을 설치한 경우로 생각하면 문제를 빠르게 풀 수 있다. 합동식의 성질을 이용하여 $memo[i]$를 구할 때마다 15746로 나누면 오버플로우가 발생하지 않는다.

아래는 세 명의 코드이다.

1. 박정우(배열)

#include <bits/stdc++.h>
#define int long long
#define float long double
#define pp pair<int, int>
#define tp tuple<int, int, int>
#define mtp make_tuple
#define mp make_pair
using namespace std;
using lf = __float128;
using ld = __int128;
float pi = 3.141592653589793238462643383279502884197169399375105Q;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int memo[1101101] = {0, 1, 2};

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 3; i < 1101101; i++) {
    memo[i] = (memo[i - 1] + memo[i - 2]) % 15746;
	}
	cout << memo[n];
	return 0;
}

2. 정연우(재귀)

#include <stdio.h>

long long padoban(long long n);

long long arr[1101101] = {0,};
int main(){

    long long num = 0;
    scanf("%lld", &num);
    printf("%lld\\n", padoban(num));

    return 0;
}

long long padoban(long long n){

    long long result = 0;
    if(arr[n] != 0){
        return arr[n];
    }
    if(n>=3){
        result += padoban(n-2)%15746;
        result += padoban(n-1)%15746;
        arr[n] = result%15746;
        return arr[n];
    }
    else if(n == 1){
        return 1;
    }
    else if(n == 2){
        return 2;
    }

    return 0;
}

3. 이하랑(재귀)

#include <stdio.h>

long long memo[1010101] = { 0, };

long long f(long long n) {
	if (memo[n] != 0) return memo[n] % 15746;
	if (n == 1) return 1;
	else if (n == 2) return 2;
	else {
		memo[n] = f(n - 2) % 15746 + f(n - 1) % 15746;
		return memo[n] % 15746;
	}
}

int main() {

	long long n;
	scanf("%lld", &n);

	printf("%lld", f(n) % 15746);

	return 0;
}