[파이썬(Python)] 백준 2133번 타일 채우기

 

 

백준 2133번: 타일 채우기

문제 바로 가기

---

📌 문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

주어진 문제는 $3 \times N$ 크기의 벽을 $2 \times 1, 1 \times 2$ 크기의 타일로 채우는 경우의 수를 구하는 문제입니다. 

 

 

 

홀수 $N$인 경우 불가능

 

$N$이 홀수인 경우에는 벽을 채울 수 없습니다. 그 이유는 $3 \times N$ 벽에는 총 $3 \times N$ 개의 칸이 있으며, 타일은 각각 2칸씩 덮을 수 있습니다. 하지만 $3 \times N$ 이 홀수라면 항상 1칸이 남게 되어 타일로 완전히 채우는 것이 불가능합니다.

 

 

예를 들어, $N = 1$인 경우에는 벽의 크기는 $3 \times 1$ 로, 총 3칸입니다. $2 \times 1$ 또는 $1 \times 2$ 타일로 한 번에 2칸을 덮을 수 있으나 항상 1칸이 남아서 완벽하게 채울 수 없습니다.  

 

 

 

 

 

$N = 3$인 경우에는 벽의 크기는 $3 \times 3$ 로, 총 9칸입니다. 2칸씩 덮다 보면 항상 1칸이 남아서 완벽하게 채울 수 없습니다.  

 

 

 

 

 

 

 

짝수 $N$인 경우 가능

 

$N$ 이 짝수인 경우 $3 \times N$ 벽의 총 칸 수 $3 \times N$이 짝수이므로 2칸 타일을 사용해 모든 칸을 정확히 덮을 수 있습니다.

 

 

 

 

 

 

 

 

 

 

아이디어

 

 

$N = 2$

 

$3 \times 2$ 크기의 벽을 채우는 경우의 수는 다음과 같이 3가지입니다.

• 가로로 $1 \times 2$ 타일 3개
• 세로로 $2 \times 1$타일 2개 + 가로로 $1 \times 2$ 타일 1개
• 가로로 $1 \times 2$타일 1개 + 세로로 $2 \times 1$ 타일 2개 

 

 

 

 

 

 

 

$N = 4$

 

$3 \times 4$ 크기의 벽을 채우는 경우의 수는 다음과 같이 나눠서 생각할 수 있습니다.

 

 

 

1. 기본 패턴으로 채우는 경우

 

$N = 4$ 벽을 $N = 2$일 때의 벽 2개로 나누어 생각합니다. 각 $N = 2$ 벽에는 3가지 경우의 수가 있으므로 이를 조합하면 $3 \times 3 = 9$ 가지 경우의 수가 있습니다. 

 

 

 

 

 

2. 특수 패턴으로 채우는 경우

 

$N = 4$ 벽만의 독특한 타일 배치가 2가지 추가로 존재합니다. 이는 $N = 4$에서만 가능한 특수한 배치로 아래 그림처럼 나타낼 수 있습니다. 

 

 

 

 

따라서 $N = 4$일 때의 총 경우의 수는 $9 + 2 = 11$입니다. 

 

 

 

 

 

일반화

 

$\text{dp}[i]$ 를 $3 \times i$ 크기의 벽을 타일로 채우는 경우의 수라고 정의합니다.

 

 

1. 기본 패턴으로 채우는 경우

 

벽의 끝부분에서 $3 \times 2$ 크기의 타일 배치를 사용하는 경우로, 이는 이전 벽 $\text{dp}[i-2]$에 3가지 경우의 수를 곱한 것입니다.

 

 

 

 

$$\text{dp}[i]_{\text{basic}} = \text{dp}[i - 2] \times 3$$

 

 

 

 

2. 특수 패턴으로 채우는 경우

 

$3 \times 4, 3 \times 6, \dots$ 등에서 독특한 배치가 발생합니다. 이 경우, 이전의 모든 $i - k \quad (k = 4, 6, 8, \dots)$에 대해 특수 패턴을 추가로 고려합니다.

 

 

 

 

$$\text{dp}[i]_{\text{unique}} = \sum\limits^{i}_{k = 4, 6, 8, \dots} \text{dp}[i - k] \times 2$$

 

 

 

최종 점화식은 다음과 같습니다. 

 

 

$$\text{dp}[i] = \text{dp}[i - 2] \times 3 + \sum\limits^{i}_{k = 4, 6, 8, \dots} \text{dp}[i - k] \times 2$$

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def tile_count(n):
    if n % 2 != 0:
        return 0

    dp = [0] * (n + 1)
    dp[0] = 1  
    dp[2] = 3  

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

    return dp[n]


n = int(input())
print(tile_count(n))