백준 알고리즘 - 2133 - 타일 채우기

문제

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

---

입력

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

---

출력

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

---

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

---

접근법

DP의 대표 유형중 하나인 타일 문제이다.

 

먼저 벽을 1x2, 2x1 크기의 타일로 채워야 하므로 3xN의 N이 홀수이면 벽을 타일로 채울 수가 없다. 

타일은 짝수 개이기 때문이다. 따라서 N이 홀수이면 경우의 수는 0 이다. 

 

N이 2인 경우 총 3가지가 존재한다.

f(2) = 3

 

N이 4인 경우 총 11가지가 존재한다.

f(4) = f(2)xf(2) + 2 = 11

 

N이 6인 경우의 수도 마찬가지로 증가한다.

N이 2인 경우의 수를 N이 4인 경우의 수만큼 11번 붙일 수 있다.

 

모든 경우의 수를 더하면 총 41가지 경우가 있다.

f(6) = f(2)xf(4) + 2xf(2) + 2 = 41

 

N이 8인 경우의 수도 마찬가지로 증가한다.

f(2)xf(6) + 4xf(4) + 6xf(2) + 2 = 153

---

코드

# N 입력
n = int(input())
Tile = [0]*31
Tile[2] = 3 # N이 2인 경우의 수

# DP
for i in range(4, 31, 2):
    Tile[i] = Tile[2] * Tile[i - 2] # N-2의 경우의 수 x 가로가 2인 타일묶음
    for j in range(4, i, 2):
        Tile[i] += 2 * Tile[i - j] # 새로운 경우의 수
    Tile[i] += 2 # 가로가 N인 타일묶음 또다른 새로운 경우의 수

print(Tile[n])