#1904번 01타일 (C++)

#include <iostream>
#define MODULE 15746
using namespace std;

int arr[1000001];

int num = 0;

int Find(int x){
    if(x<=2) return x;
    else if(arr[x]) return arr[x];
    return arr[x]= (Find(x-2) + Find(x-1)) % MODULE;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i=0; i<2; i++) arr[i] = i;

    cin >> num;
    cout << Find(num)%15746;

    return 0;
}

손으로 끄적여본 결과, 피보나치 수열의 공통점과 유사한 식을 가졌던 점이 신기했다. 

다만 해당 식을 arr[x] = Find(x-2) + Find(x-1)로 하면 오답이 나오고

arr[2] = Find(x-2) + Find(x-1) % 15746을 해야 정답이 나온다.