Problem

https://www.algospot.com/judge/problem/read/ASYMTILING

Idea

2*1 로 만들 수 있는 총 경우의 수는..

int f(int n) {
    if (n <= 1) {
        return 1 
    }
    int ret = cache[n];

    if (ret != -1) {
        return ret;
    }
    ret = (f(n-1) + f(n-2)) % MOD;
    cache[n] = ret;
    return ret;
}

O(N): 부분 문제의 수는 O (n) 이고， 각각의 값을 계산하는 데는 O(1)

대칭을 제외한 비대칭 경우의 수는?

• 대칭인 경우의 수를 뺀다

n이 홀수일 경우:
a) 가운데 21이 하나 있는 경우 1가지, n-1 은 서로 대칭 (다시 분할)

n 이 짝수일 경우:
b) 가운데 21 가 2개 경우와 n-2 는 서로 대칭 (다시 분할)
c) 전체의 반이 서로 대칭인경우. n / 2 (다시 분할)

int solution(int n) {
    if (n % 2 == 1) {
        return f(n) - f(n/2); // a)
    }
    int ret = f(d);
    ret = ret - f(n/2 -1); // b)
    ret = ret - f(n/2); // c)
    return ret;
}

• 비대칭인 경우를 센다 한쪽이 아닌 양쪽에서부터 타일링한다고 보면
  대칭인 경우는:
  a) 21 이 양쪽끝에 존재
  b) 21 2개가 양쪽끝에 존재
  
  비대칭인 경우는:
  c) 왼쪽은 21, 반대쪽은 21 2개 가로로
  d) 오른쪽이 21, 반대쪽은 21 2개 가로로
  
  

  int solution(int n) { // 비대칭 수를 반환한다
    if (n <= 2) return 0; // 비대칭 경우 없음
    int ret = memo[n];
    if (ret != -1) return ret;
  
    ret = solution(n-2); // 양쪽 1개씩 버리고 나머지 다시 분할해본다
    ret += solution(n-4); // 양쪽 2개씩 버리고 다시 분할
    ret += f(n-3); //왼쪽 1개, 오른쪽 2개 버리고 카운팅
    ret += f(n-3); //왼쪽 2개, 오른쪽 1개 버리고 카운팅
    return ret;
  }
  

  
  (A + B) mod C = (A mod C + B mod C) mod C
  (A - B + C) mod C