[Python] 2133 - 타일 채우기 (골드4)

1. 문제 설명

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

2133번: 타일 채우기

실버의 타일링(BOJ - 1793) 문제를 풀어봤다면 쉽게 해결할 수 있는 문제

---

2. 아이디어

어느정도 패턴 분석이 될 때까지는 노가다를 해봐야 하는 문제다.

N이 홀수인 경우에는 절대 타일을 모두 채울 수 없으므로 0을 출력 후 프로그램을 종료하면 된다.

그럼 결국 남는 경우의 수는 N이 짝수인 경우일 뿐인데

 

N이 2, 4 정도는 직접 세볼 수 있지만 6만 넘어가도 41가지 경우가 나온다.

처음에 규칙성을 찾기가 굉장히 힘들지만 표를 그려서 색칠해보면 이해하기 쉽다.

2x3 블럭이 만나면 접선에 가로로 블럭을 놓은 이러한 형태의 타일이 나오면서

점화식이 조금 복잡해지는 건데 직접 해보면 감을 잡을 수 있다.

 

N이 8인 경우를 생각해보자.

이 경우는 N이 6인 케이스에서 2x3 타일이 더 들어왔다고 봐도 무방하다.

따라서 처음은 cache[6] x cache[2]

그리고 이번에 위에서 언급한 새롭게 고려해주어야 할 형태의 타일이 나오는데

저 사이에는 무조건 가로로 타일이 놓여져야한다. (그래야 4x3 타일이 온전히 채워진다.)

특수한 형태의 타일이 오른쪽에 놓이느냐, 왼쪽에 놓이느냐에 따라

경우의 수가 2개로 갈라지므로 cache[6] x 2가 된다.

위의 경우와 똑같다.

좌, 우의 경우를 고려하여 cache[2] x 2의 경우가 나온다.

그리고 가장 마지막 형태인데, 이때는 가로로 놓인 타일이 위쪽으로 올라가는 경우가 존재하므로

고정적으로 2라는 값이 나온다.

 

이 일련의 과정을 보면 dp를 사용하여 결과를 구하는 것은 총 3가지 과정으로 나눌 수 있다.

1. N-2 경우의 수에 2x3 크기의 타일이 추가된 경우 고려
2. 4부터 N-2까지 모든 경우에 2를 곱하여 경우의 수에 더함
3. 최종적으로 2를 더함

놀랍게도 이 문제는 이게 다였다. 그다음은 반복문 조건을 잘 걸어가며 돌려주면 끝나는 문제.

 

---

3. 코드

cache = [0] * 31

def solution():
    n = int(input())
    cache[2], cache[4] = 3, 11
    if n % 2 == 1:
        print(0)
        return
    
    for i in range(6, 31, 2):
        cache[i] = cache[i - 2] * cache[2]
        for j in range(4, i, 2):
            cache[i] += 2 * cache[i - j]
        cache[i] += 2
    print(cache[n])
    
solution()