11726 2xn 타일링

#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)) % 10007;
}
 
int main() {
    scanf("%d", &n);
    printf("%d", f(n));
}

가로 칸만 세면 1x2는 1칸을 차지하고 2x1은 2칸을 차지한다.

다른 말로 i-2에서 2x1로 2칸을 차지하는 방법 한 개와 i-1에서 1x2으로 1칸을 차지하는 방법 한 개가 있는 것이다.

점화식으로 세우면 dp[a] = (f(a - 1) + f(a -2)) % 10007으로

피보나치와 같은 식인 것을 알 수 있다.