N이 짝수일 때만 타일을 채울 수 있다. 3xN 벽은 3x(N-2), 3x(N-4)... 을 조합해서 만들 수 있다. 3xN 벽에는, 3x(N-2), 3x(N-4).. 에서 볼 수 없었던 고유의 패턴이 생긴다.
위의 내용을 조합하면, 3xN 의 모든 경우는
3x(N-M)의 모든 경우 x 3xM 고유의 경우
로 recursive 하게 쪼개서 구할 수 있다.
이때, sub-problem이 반복하기 때문에, 다음의 수식을 통해서 DP의 Bottom-Up 방식으로 풀 수 있다.
dp[i] = dp[i-2]*3 + dp[i-4]*2 + dp[i-6]*2....
dp[N+1]
시간 복잡도는 O(N^2)이다.