[python] 백준 2133 타일 채우기

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

문제 해결

$ 3 \times N$ 행렬에서 N이 홀수일 경우는 타일을 다 채울 수 없다.

N이 짝수인 것은 명백하고 타일을 채우는 방법은 2X2, 2X4 .... 무척 다양하다.

하지만 다양해도 확실한 것은 짝수로 끝난다는 것이다.

이전 dp와 관련없이 만들어지는 타일 채우는 가지수는 +2가 있다.

중간의 dp와 연결되지 않고 만들어지는 가지수 1

 

중간의 dp와 연결되지 않고 만들어지는 가지수 2

따라서 다음과 같이 코드를 짤 수 있다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
dp = [0 for i in range(31)]
dp[2] = 3 # 직접 셈
for i in range(4,31,2):
    dp[i] = dp[2]*dp[i-2]
    for j in range(4,i,2):
        dp[i] += 2*dp[i-j]
    dp[i] += 2
print(dp[n])