[백준/2133] 타일 채우기 (Python)

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

2133번: 타일 채우기

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:14:02

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

2

 

출력 예시

 

3

 

 

---

 

풀이

 

DP문제의 바이블 중 하나. 또한 어렵게 내려면 얼마든지 어렵게 낼 수 있는 문제 중의 하나. 그 아비규환의 역사 중 일부가 아래 링크에 담겨 있다...

 

2023.04.14 - [알고리즘 문제/프로그래머스] - [프로그래머스/LV3] 아방가르드 타일링 (Python)

[프로그래머스/LV3] 아방가르드 타일링 (Python)

 

그래도 기본이 기본인 만큼, 경우의 수를 짚고 넘어가 보자.

우선, 2x3 타일이 오는 경우는 크게 3가지이다.

 

즉 M x 3 크기의 타일의 경우의 수가 있다면, 다음 (M + 2) x 3 크기의 타일의 경우의 수는 이에 3을 곱하여 더해 줄 수 있다(경우의 수가 3가지이므로)

 

또한, 2n x 3 타일이 오는 경우는 크게 2가지이다.

n이 아무리 커지더라도 이 패턴이 반복된다. 앞선 경우와 같이 각 경우의 수에 2를 곱하여 더해주면 다음 경우의 수를 업데이트 할 수 있다. 이런 식으로 모든 짝수에 대해 고려하면 쉽게 풀이 가능하다. 물론, 세로 면적이 넓어지거나 타일 형태가 바뀌면 이런 패턴화가 좀 더 복잡해지고, 풀이 역시 이런 엣지 케이스를 고려해야 하다 보니 더 난도가 올라간다.

 

 

풀이 코드

N = int(input())
dp = [0]*(N+1)
dp[0] = 1
for i in range(2, N+1, 2) :
  for j in range(2, i+1, 2) :
    mul = 3 if j == 2 else 2
    dp[i] += dp[i-j] * mul
print(dp[-1])

풀이 완료!