Tiling(3n)

3xn 크기의 벽을 1x2, 2x1 타일로 채울 수 있는 경우의 수를 구하는 문제

DP는 작은 소문제로부터 점화식을 도출해서 전체문제(D[n]) 최종적인 해를 구하는 것이다.

이 문제도 2xn 타일링 문제와 마찬가지로, 마지막에 올 수 있는 타일의 경우의 수를 구해보면 다음과 같은 3가지 경우가 있다.

마지막에 올 수 있는 타일의 경우의 수

d[n] = d[n-2] * 3 을 도출해낼 수 있다.

하지만 다음과 같은 예외들을 생각할 수 있다.

1. n이 4이상부터는 각각의 경우에 대해 경우의 수가 2가지씩 더 나오는 것을 알 수 있다! d[4] = 3x4 경우의 수를 대략 그려보면 각각의 경우에 대 위 아래 상하가 반전된 2가지의 경우가 나올 수 있다!

2. n이 짝수의 경우만 해당되는 것을 알 수 있다!

3. 1,2를 조합해서 보면 d[n] = d[n-2]*3 + d[n-4]*2 + d[n-6]*2 + ... n은 4부터 2가지씩 추가된다는 것을 점화식으로 표현할 때 예를 들어 n이 4라면 d[2] = 3x2 벽 채우는 타일 경우의 수 = 3

   d[4] = d[2]*3 + d[0]*2 d[6] = d[4]*3 + d[2]* + d[0]+*2 ...

3n 부터는 직접 그리는 것은 권장하지 않고, 이러한 문제와 풀이방법은 참고하고 넘어가도록 한다.