[백준] 2133. 타일 채우기 풀이

2133번: 타일 채우기

 

2133. 타일 채우기

이 문제는 개인적으로 패턴을 찾아내기까지 시간이 매우 오래걸렸습니다. 6칸짜리 타일까지 일부 만들어보던 중 4칸부터 모든 칸에 2개씩의 족보없는 타일이 들어간다는 것을 알게된 후부터 어느정도 파악하게 되었습니다.

 

접근한 방법

일단 홀수 칸들은 어떻게 생각해봐도 만들어질 수가 없으니 제외했고, 머리가 좋지않은 저는 일단 4칸까지는 그냥 그려봤습니다. 

그려봤을 때 2칸에서 만들어진 3가지 패턴이 이후 패턴에서도 사용되는 것을 볼 수 있었죠. 즉 4칸에서 2칸을 채우는 용도로 보자면 3개의 패턴이 3번씩 채워지는 것을 볼 수 있습니다. 그러면 9가지가 만들어지고 추가로 2개의 족보없는 패턴이 나오게 됩니다.

혹시 이후 칸에서도 족보없는 패턴이 나오나 하여 비슷한 모양으로 만들어보면 딱 2개로 나옵니다. 사실 생각해보니 3가지 패턴이 사용되는 경우는 마지막 2칸을 채우는 경우인데 3가지 패턴을 사용하지 않는다면 저 모양의 틀에서 바뀔 수가 없습니다.

 

그러면 정리할 수 있습니다.

각 칸들은 3개의 패턴이 한번씩 채워들어가니 이전 칸에서 고려되었던 경우 * 3만큼의 경우를 우선 가집니다.

그리고 2개의 족보없는 패턴을 한번씩 채울 수 있으니 이전 칸을 제외한 각 칸들에서 고려되었던 경우 * 2만큼의 경우를 추가로 가지고 현재 채우고있는 칸에서 2개의 족보없는 패턴이 또 나오기 때문에 +2를 해줍니다.

 

무슨 말이느냐 하면 예를 들어 8칸이 만들어지는 경우를 그림으로 봅시다.

1) 3가지 패턴이 이전 칸인 6칸 경우에 채워들어가므로 6칸 경우 * 3만큼 채워집니다. + (41 * 3)

2) 4칸에서 발생한 족보없는 패턴 2가지가 4칸 경우 * 2만큼 채워집니다. + (11 * 2)

3) 6칸에서 발생한 족보없는 패턴 2가지가 2칸 경우 * 2만큼 채워집니다. + (3 * 2)

4) 8칸에서도 족보없는 패턴이 2가지가 나오므로 +2를 해줍니다.

 

이렇게 해서 8칸은 총 123 + 22 + 6 + 2 = 153의 경우가 만들어집니다.

 

이 문제는 이전 칸에서 계산한 값이 그대로 사용되므로 DP로 해결할 수 있고 점화식으로 표현하면 아래와 같습니다.

테이블[i] += 테이블[i - 2] * 3
테이블[i] += 테이블[j] * 2 (j = 0, while j <= i - 4)

 

 

작성 코드 (Python)

import sys
input = sys.stdin.readline

n = int(input())
table = [1] + [0] * n
for i in range(2, n + 1, 2):
    table[i] += table[i - 2] * 3
    for j in range(0, i - 2, 2):
        table[i] += table[j] * 2
print(table[n])

작성 코드 (JavaScript)

function solution(n) {
  const table = Array(n + 1).fill(0);
  table[0] = 1;
  for (let i = 2; i <= n; i += 2) {
    table[i] += table[i - 2] * 3;
    for (let j = 0; j <= i - 4; j += 1) table[i] += table[j] * 2;
  }
  return table[n];
}
solution(8);