[백준 11727] 2×n 타일링 2 [Python]

 

 

---

기존 문제의 응용문제다.

[백준 11726] 2×n 타일링 [Java]

 

점화식 정의는 기존과 동일하다.

dp[i] : 2xi 크기의 타일을 채우는 모든 경우의 수 

 

하지만 이번에는 2x2 공간에 대해 1x2 뿐만 아니라 2x2으로도 채울 수 있다.

n = 1 일때 1 : 2x1

n = 2 일때 3 : 2x1, 1x2, 2x2

 

마찬가지로 n >= 3 부터는 아래의 점화식이 성립한다.

dp[i-1] = 2x1 1개

dp[i-2] = 1x2 2개

dp[i-2] = 2x2 1개

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 2]

문제 조건에 따라 MOD(10,007)로 나눈 값을 dp에 담아주자.

---

소스코드

보기

---

출처

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