11727 2xn 타일링2

#include <stdio.h>
 
#define NM 1000
int n, dp[NM+1];
 
int f(int a /*i*/) {
    if (a == 0 || a == 1) return 1;
    if (a < NM && dp[a] != 0) return dp[a];
 
    return dp[a] = (f(a - 1) + f(a - 2)*2) % 10007;
}
 
int main() {
    scanf("%d", &n);
    printf("%d", f(n));
}

11726번(http://foxtrotin.tistory.com/71)에서 2x2의 경우가 추가되었다.

i-1에서 1x2로 채우는 방법과

i-2에서 2x1로 채우는 방법 + 2x2로 채우는 방법이 있으므로

점화식은 dp[a] = (f(a - 1) + f(a -2)*2) % 10007 가 된다.