[Python - Dynamic Programming] 2133 타일 채우기

📌 문제

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

재귀를 통해서 완성된 조건을 풀 수 있을 것 같아보였다. 그런데 시간이 좀 오래 걸릴 것 같아서 DP를 사용했다.

 

DP가 사용 가능한 이유는 이전 값을 참고하여 현재의 값을 구할 수 있기 때문이다.

 

일단 3 X 2의 타일이 있을 때,

위와 같이 3개의 배치가 가능하다.

 

그 다음 3X3 의 타일 배치를 구하려고 했는데, 절대로 배치를 할 수가 없었다. 직관적으로 생각해보면, 3X3은 9개의 타일이 필요한데, 2X1 타일을 아무리 배치한들 8이라는 짝수로 채워지기 때문에 남은 타일 1개를 절대 충족 시킬 수 없기 때문이다.

 

그 다음은 3X4의 경우이다.

3X4 는 다르게 표현하면 3X2 + 3X2 이다. 즉, 3X2 타일을 두 번 사용하는 것이다. 이때 각각의 타일은 독립 시행이기 때문에 3X2의 경우의 수와 3X2의 경우의 수를 곱하여준다. 그래서 총 9개의 경우의 수가 생긴다.

 

그런데 여기서 3X4는 2가지 경우의 수가 더 있다.

 

이 두 개의 타일은 이전 시점을 참고하지 않고 자체적으로 만들어내는 경우이다.

 

이때, 가장 최초에 가능한 타일의 배치 경우의 수가 3개이다. 이를 참고하여, 다음 n(2의 배수)은 n - 2 를 3배수로 가진다.

그리고, 자체적으로 만들어내는 타일 배치는 두 가지가 있다. 그런데, 이 타일 배치는 앞선 3배수에서의 예외로 2배를 더 곱해주어야 한다.

 

더 자세히 3X6 타일을 예로 설명하면,

이와 같이 3배수를 한 타일은 3X4타일에서 오른쪽에 3X2를 붙인 형태이다. 이때, 오른쪽 말고 왼쪽에 붙인 경우의 수를 고려하여 3배수에 다시 두 배를 곱하지 않은 이유는 중복이 발생하기 때문이다.

 

하지만, 앞서 자체적으로 제작한 3X4의 타일 배치는 왼쪽에 붙여도 중복이 되지 않는다.

 

왜냐하면 3X2는 가운데를 기준으로 좌우를 나누었을 때, 가로 폭이 같기 때문에 중복이 발생하지만, 3X4와 3X2를 연결할 때는 그렇지 않아서 개별적으로 구해주어야 하기 때문이다.

 

즉, 3X6 타일은 3X4타일에 3을 곱한 후에 다시 자체적으로 제작한 타일에 2를 곱해서 더해준다. 그리고 여기서 자체적으로 제작한 타일이 존재하기 때문에 그 타일을 곱해준다. 즉 정리하면 아래와 같다.

 

1. n - 2 경우의 수에 3을 곱하여 더해준다.
2. n - 4 경우의 수에 2를 곱해 더해준다(n - 2 타일이 자체적으로 제작한 타일은 n - 4의 타일에 이어 붙인 형태이기 때문이다.
3. n - 6 경우의 수에 2를 곱해 더해준다(위와 동일한 매커니즘).
4. ...
5. n - n 경우의 수에 2를 곱해 더해준다.

3X4에서 자체적으로 제작한 타일은 아무 기반이 없이 만들었으며 총 두 가지 경우가 있었는데, 이는 3X0에 이어 붙여서 만든 경우이다. 그렇기에 3X0에서 2를 곱해준 것이다. 동일하게 3X6은 3X2에서 2를 곱하여 준다. 이 경우에서는 3X2의 타일에 3X4에서 자체적으로 제작한 타일을 이어 붙이는 경우가 2배 있기 때문에 그것을 곱해주는 것이다. 앞서 게시한 사진 속 2개의 경우가 그중 하나이다.

 

여기서 3X6에서도 이전 시점을 참고하지 않고 자체적으로 제작할 수 있다. 이것은 3X0 타일에서 오른쪽으로 타일을 생성한 경우다.

이렇게 하면 점화식을 만들 수 있다.

$$a_n = 3a_{n-1} + \sum_{k=2}^{n}2(a_{n - 2k}) (n >= 2k)$$

👨‍🏫 문제 풀이

📄 전체 코드

d = [0] * 31

d[0] = 1

n = int(input())

for i in range(2, n + 1):
    d[i] = d[i - 2] * 3
    for j in range(4, n + 1, 2):
        d[i] += d[i - j] * 2

print(d[n])

📄 준비

d = [0] * 31

d[0] = 1

n = int(input())

d[0]을 제외하고 모두 0으로 초기화해준다. d[0]은 d[n - k]에서 접근해 d[0] * 2를 해줄 것이기 때문이다.

📄 풀이

for i in range(2, n + 1):
    d[i] = d[i - 2] * 3
    for j in range(4, n + 1, 2):
        d[i] += d[i - j] * 2

print(d[n])

📌 총평

다행히 풀었다,, 진짜 어렵네