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

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

---

풀이

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

n = 1 일때 1 : 2x1타일 1개로 채우는 방법

n = 2 일때 2 : 2x1, 1x2 타일을 각각 2개로 채우는 방법

n >= 3에 대해서는 점화식을 세울 수 있다.

dp[i - 1]에 대해 2x1타일을 1개 붙이거나, dp[i - 2]에 대해 1x2 타일을 2개 붙이는 경우를 활용할 수 있다.

이때, dp[i - 2]에 대해 2x1타일을 2개 붙이는 경우는 이미 dp[i - 1]을 구할 때, dp[i - 2]에 2x1 타일을 1개 붙이는 경우가 포함되어 있기 때문에 중복되는 경우로 고려하지 않는다.

즉, 각 상태의 이전 상태에서는 중복을 고려해 현재 타일을 채우는 모든 경우의 수를 모두 담았기 때문에, 고려하지 않는다.

따라서 다음과 같은 점화식이 성립한다.

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

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

---

소스코드

보기

---

출처

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