[백준] 2133 타일 채우기 - 파이썬

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

2133번: 타일 채우기

---

DP로 해결할 수 있는 문제입니다. 따라서 점화식을 세워야 합니다. 최종 점화식은 아래와 같습니다.

 

DP[N] = DP[N-2] * 3 + DP[N-4] * 2 + ... + DP[0] * 2 ( N >= 4인 짝수)

 

점화식을 이해하기 위해서 N을 1에서 부터 대입하여 직접 그림을 그려 보아야 할 것입니다.

 

1. N = 1
3 * 1 크기의 타일을 채워야 하지만, 주어진 1 * 2 와 2 * 1 타일로 채울 수 없습니다.

 

2. N = 2

3. N = 3

3 * 3 크기의 타일을 채울 수 있는 경우의 수는 N = 2인 경우와 N = 1인 경우의 조합으로 구할 수 있습니다. 하지만 N = 1인 경우는 만들 수 없기 때문에 N = 3 인 타일을 채울 수 있는 경우는 없습니다. 따라서 N이 홀수인 경우 타일을 채울 수 있는 방법은 없다는 것을 알 수 있습니다.

 

4. N = 4 ( DP[4] = DP[2] * 3 + DP[0] * 2)

 * 

3 * 2 타일을 채운 경우와

새로운 2가지 경우를 만들 수 있습니다.

 

4. N = 6 ( DP[6] = DP[4] * 3 + DP[2] * 2 + DP[0] * 2)

3 * 4의 타일을 채운 경우의 수에서 3 * 2 타일을 채운 경우의 수를 곱합니다.

 

그리고 주의해야할 점은 3 * 4의 오른쪽에 3 * 2 타일을 채웠기 때문에 3 * 4에서 나타난 새로운 도형 2개의 왼쪽에 3 * 2 타일을 채우는 경우를 포함해야 합니다.

그리고 또 새로운 경우 2가지를 만들 수 있습니다.

 

 

5. N = 8 ( DP[8] = DP[6] * 3 + DP[4] * 2 + DP[2] * 2 + DP[0] * 2)

 

아직까지 0 ~ N-4에서 DP 값에 2를 왜 곱하는지 이해하지 못할 수 있을 것 같아 최대한 자세히 설명해 보겠습니다.

 

N = 8인 경우를 만들기 위해서

 

N = 6인 경우에서 N = 2인 경우를 곱합니다. 하지만 이는 3 * 6인 타일 오른쪽에 3 * 2 타일을 이어 붙인 것만 고려하기 때문에 N = 6에서 새로 만들어진 2가지 타일의 왼쪽에 3 * 2를 이은 경우를 포함하지 않습니다. 따라서 DP[2]에 2를 곱한는 것 입니다.

 

N = 4인 경우도 위와 동일합니다.

 

그리고 N = 0인 경우는 문제에서 주어진 N의 범위를 넘지만, DP[0]을 1로 초기화 한다면 굳이 2를 따로 더하지 않고

0 ~ N-4까지 2를 곱하는 것으로 점화식을 통일 할 수 있습니다.

 

Python