[BOJ][🟡4][백준#02133] 타일 채우기

문제 출처

BAEKJOON Online Judge #2133

문제

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

입력

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

출력

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

예제

입력

2

출력

3

My Sol

def main():
    N = int(input())
    if N%2: return 0
    M = max(N+1, 3)
    T = [0]*M
    T[2] = 3

    i = 4
    acc = 1
    while i<=N:
        T[i] = 3*T[i-2] + 2*acc
        acc += T[i-2]
        i += 2
    return T[N]

print(main())

DP를 사용하는 대표 문제인 타일 문제의 응용 문제였다.

1. N을 입력받는데, N이 홀수이면 홀수x홀수=홀수 이므로 넓이가 2 단위인 블럭들로 채울 수 없어 항상 경우의 수는 0이다. 이를 가지치기 해준다.
2. DP 배열을 T로 두고 초기화 한 뒤, 길이가 2인 경우 3개의 경우가 있음을 초기화한다.
3. 너비가 N인 경우(T[N]) 너비가 N-2인 경우(T[N-2])인 경우에 너비가 2인 경우, 3가지를 곱한 3T[N-2]와 함께 서로 교차하는 경우를 acc에 누적하여 더해주며 곱했다. acc에 2를 곱해 T[n]에 더하는 이유는, 대체 불가능한 교차 블럭은 2x1로 계속 이어진 가로줄이 위, 아래 2가직 경우를 가지기 때문이다. 그리고 만약 이것이 중간에 3연속 이어져 매끄럽게 잘라낼 수 있는 경우라면 위의 3씩 곱하는 연결에 포함되므로 이는 제외한다.

결과

맞았습니다!!