ASYMTILING (중, p. 259)

소요 시간: 30분

책 난이도는 ‘하’였는데, ‘중하’도 아니고 ‘중’수준인 듯 하다.

점화식 자체는 데칼코마니같은 경우를 빼지 않을 때를 먼저 구하고,

여기서 데칼코마니 경우를 빼주면 된다.

여기서 처음에는 그래서 x칸의 타일을 채우는 방법은 f(x) - f(x/2)라고 생각했으나,

x가 짝수일 땐 f(x)-f((x-1)/2)-f(x/2)가 된다.

잘 생각해보면,

단순히 f(x)-f(x/2)라 하면, 짝수일 때 중앙에 블록이 2x1짜리가 왔을 때 ………||……… ← 이런 형태가 된다.

근데 이 점화식으론 ………=……… ← 이런 경우의 수를 셀 수 없다.

즉, f(x)에서 x가 짝수일 때, 아래 2가지 경우를 빼줘야 한다.

………||……… → f(x/2)

………=……… → f((x-1)/2)

이러한 점화식을 생각해내는게 어렵진 않지만, 위의 -f(x/2)-f((x-1)/2)부분을 -2*f(x/2)로 간과하기 쉬운 것 같다.

여기서 헤매기 시작하면 문제푸는데 상당히 오래걸리고, 모듈러 연산할 때 (x-y)%M == (x-y+M)%M인 것도 알아야 하기때문에 난이도 ‘하’라고 하기엔 무리가 있다.

난이도 ‘중하’로 하려했으나 위처럼 고려해야 할 부분이 여러 개 있고, 생각보다 오랜 시간이 걸릴 수 있을 것 같아 ‘중’으로 조정했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9+7;
bool fchk[101], gchk[101];
ll fdp[101], gdp[101];
ll f(int x) {
    if(x<=1) return 1;
    if(fchk[x]) return fdp[x];
    fchk[x] = true;

    return fdp[x] = (f(x-1)+f(x-2))%M;
}
ll g(int x) {
    if(x<=1) return x^1;
    if(gchk[x]) return gdp[x];
    gchk[x] = true;

    ll & ret = gdp[x];
    if(x%2==0) ret = (f(x)-f((x-1)/2)-f(x/2)+2*M)%M;
    else ret = (f(x)-f(x/2)+M)%M;
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        printf("%lld\n", g(n));
    }
    return 0;
}