문제

• 
• 시간 제한: 2초
• 메모리 제한: 128 MB

Problem Analysis

N이 짝수일 때만 타일을 채울 수 있다. 3xN 벽은 3x(N-2), 3x(N-4)... 을 조합해서 만들 수 있다. 3xN 벽에는, 3x(N-2), 3x(N-4).. 에서 볼 수 없었던 고유의 패턴이 생긴다.

Algorithm

위의 내용을 조합하면, 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.... 

Data structure

dp[N+1]

결과

Other

시간 복잡도는 O(N^2)이다.