[백준] 2133번 타일 채우기 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1 (연습)

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

우선, n이 홀수일 경우엔 타일을 모두 채울 수 없다. 이후, 예시를 통해 살펴보자

n = 2

n = 4

n = 4일때 이처럼 dp[2] 일때 dp[2]를 붙인 모양과 새로운 패턴 2개가 추가된다.
따라서 dp[4] = dp[2] * dp[2] + 2가 된다.

이처럼, n이 증가 할때마다 새로운 패턴이 추가된다는 점을 유의해야한다. 이는 당연하게도 점화식에도 영향을 미치게 되고, 모양은 이처럼 만들수 있다.

이 점을 유의하여 점화식을 유도해 본다면,

dp[n] = dp[n - 2] x dp[2] + dp[n - 4] x 2 + dp[n - 6] x 2 + ... + dp[2] x 2 + 2

이때 파란색 부분은 dp[n - 2]에 dp[2]를 붙이는 경우의 수,
빨간색 부분은 각 n-2부터 2까지 추가되는 새로운 패턴끼리 붙을 수 있는 경우의 수이다.
또한 마지막 +2(초록색) 부분은 새롭게 추가되는 패턴의 경우의 수이다.

따라서 이를 정리하여 점화식을 코드로 작성해보면 아래와 같다.

	dp[i] += dp[i - 2] * dp[2]
    dp[i] += sum(dp[:i - 2]) * 2
    dp[i] += 2

---

📒 코드

n = int(input())
dp = [0 for _ in range(n + 1)]
if n > 1:
    dp[2] = 3

for i in range(4, n + 1, 2):
    dp[i] += dp[i - 2] * dp[2] # 파란색
    dp[i] += sum(dp[:i - 2]) * 2 # 빨간색
    dp[i] += 2 # 초록색

print(dp[n])

---

💭 후기

계속해서 새로운 패턴이 추가되고, 이를 점화식을 세울 때 반영해야 한다는 점이 많이 까다로웠던 문제.

---

🔗 문제 출처

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

---