[BOJ/python3] 2133번 타일 채우기

 

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

2133번: 타일 채우기

---

문제

3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수

 

풀이

DP로 풀면 된다.

11726번 2xn 타일링과 비슷하지만 풀이는 조금 달랐다.

[BOJ/C++]11726번 2xn 타일링

처음에 위 문제대로 현재 위치 기준으로만 벽돌 경우를 세다가 애를 먹은 문제...

 

어떤 규칙으로 블록을 채울 수 있는지 생각하고, 그에 맞춰 문제를 풀면 된다.

우선, N이 홀수인 경우는 블록을 채울 수 없다.

 

 

N이 짝수인 경우 다음과 같은 룰로 블록이 추가된다.

i-2인 경우를 제외하고는 다음과 같이 짝수단위로 두 가지의 경우가 있다.

 

 

소스코드

def block(n):
    dp = [0]*31
    dp[0] = 1
    dp[2] = 3

    if n%2 != 0:
        return 0
    if n == 2:
        return dp[2]

    for i in range(4, n+1, 2):
        dp[i] += 3*dp[i-2]
        for j in range(4, i+1, 2):
            dp[i] += 2*dp[i-j]
    return dp[n]


n = int(input())
print(block(n))