[백준] 11727번 2xn 타일링 2 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1

---

---

---

💡 문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

💭 접근

11726번 2xn 타일링 문제와 비슷한 문제이다.

도형을 그리는 경우의 수를 그려보면,
n = 1(1가지), 2(3가지) 일때,

n = 3(5가지) 일때, dp[3] = dp[2] + dp[1] x 2

n = 4(11가지) 일때,dp[4] = dp[3] + dp[2] x 2

따라서 점화식은 dp[i] = dp[i - 1] + dp[i - 2] x 2 로나타낼 수 있다.

---

📒 코드

n = int(input())
dp = [0, 1, 3]

for i in range(3, n + 1):
    dp.append((dp[i - 1] + dp[i - 2] * 2) % 10007)

print(dp[n])

---

💭 후기

11726번 2xn 타일링 문제와 비슷하게 경우의 수를 직접 구하여 패턴을 찾아 점화식을 도출하였다.

---

🔗 문제 출처

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

---