GRID

https://algospot.com/judge/problem/read/GRID

algospot.com :: GRID

#점화식으로 해결함.

기존의 f(N)의 값에서 f(N+1)을 구하는 식은 다음과 같음.

f(N+1) =  f(N)        // 그냥 2x1타일 2개를 세로로 붙였을 경우

+ f(N-1) * 5 // 4x2 판을 채우는 경우 (5개)

+ f(N-2)     // 'ㄷ' 좌우반전 모양을 만드는 경우

- f(N-3)     // f(N-2)의 경우에 기존의 모양과 달리 ㄷ자가 되므로 중복된 경우를 빼야함

 

#include 

int DataSet[1001];
int main()
{
	DataSet[0] = DataSet[1] = 1;
	DataSet[2] = 5;
	DataSet[3] = 11;

	for (int i = 4; i < 1001; i++)
		DataSet[i] = DataSet[i - 1] + DataSet[i - 2] * 5 + DataSet[i - 3] - DataSet[i - 4];

	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		int W;
		scanf("%d", &W);

		printf("%d %d\n", i, DataSet[W]);
	}
	return 0;
}