[코드업] 3728 - 블럭 채우기 8

2∗1의 직사각형 블럭을 이용하여 4∗n 크기의 직사각형 모양으로 채우려고 한다.

가능한 방법의 수를 구하여라. 2∗1직사각형 블럭은 무한정 있다고 가정한다.

이 때 숫자가 커질 수 있으므로 100,007로 나눈 나머지를 출력하시오.

#include<iostream>
using namespace std;

const int DIV = 100007;
int dp[10001] = {0, 1, 5,};

int block(int n){
	if(dp[n] != 0) return dp[n];
	
	int sum = 0;
	for(int i = 1; i < n; i++){
		if(i == 1)
			sum += block(n - i);
		else if (i == 2)
			sum += block(n - i) * 4;
		else{
			if(i % 2 == 0) sum += block(n - i) * 3;
			else sum += block(n - i) * 2;
		}
	}
	return dp[n] = (n % 2 == 0) ? (sum + 3) % DIV : (sum + 2) % DIV;
}


int main(){
	int N;
	cin >> N;
	cout << block(N);
	
	return 0;
}