[코드업] 3716 - 블럭 채우기 5

3∗1∗1블럭과 3∗2∗1 블럭을 이용해서 3∗n∗1블럭 판을 맞추려고 한다.

가능한 모든 가짓수를 1,000으로 나눈 나머지를 구해보자

#include<iostream>
using namespace std;

const int DIV = 1000;
int dp[10001] = {0, 1, 2, 6,};

int block(int n){
	if(dp[n] != 0) return dp[n];
	return dp[n] = (block(n - 3) * 3 % DIV + 
			block(n - 2) % DIV + 
			block(n - 1) % DIV) % DIV;
}


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