BOJ 2133 타일 채우기

www.acmicpc.net/problem/2133

2133번: 타일 채우기

2xN 타일링 문제랑 똑같을 줄 알고 만만히 봤다가 죽을상 짓게 만든 문제다.

 

답안 코드

[Python3 코드]

from sys import stdin
input = stdin.readline


def solution(N):
    # dp[n] : 3*n 인 타일을 채우는 경우의 수
    # dp[n] = dp[n-2]*dp[2] + dp[n-4]*2 + dp[n-6]*2 + ...
    ## 2 곱하는 이유 : 예외 케이스

    dp = [0 for _ in range(31)]
    dp[0] = 1
    dp[2] = 3

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

    return dp[N]


N = int(input())
print(solution(N))

 

풀이

3 x N 의 벽을 맞출 때, N에 따라 다음과 같은 규칙이 붙는다.

 

1. N이 홀수면 dp[N]=0 이다.

이건 조금만 생각해보면 되니까 패스

 

2. dp[2] = 3 이다.

dp[2]의 경우의 수는 3이다.

3. N이 4 이상 짝수이면, '예외 케이스'가 2개 생긴다.

예를 들어, N=4면 dp[4]는 다음과 같다.

dp[4]의 경우의 수는 11이다.

 

N=6, N=8 ... 등의 경우에도 직접 그려보면 마찬가지로 항상 예외 케이스 2개가 발생한다.

 

 

점화식 세우기

잠시 2 x N 타일링을 떠올려보면 그때의 점화식은 다음과 같았다.

 

2 x N 타일링의 점화식

하지만 3 x N 타일링의 경우, 4 이상인 모든 짝수인 N에 대해서 항상 예외 케이스가 2개씩 발생한다. 

즉, 2 x N 타일링과 달리, 점화식을 짤 때 모든 N을 돌아봐야 한다. 

 

어차피 N이 홀수인 경우의 수는 0이니까, 뒤에서부터 짝수로 잘라서 생각해보면 된다.

dp[6]의 경우의 수는 41이다.

이미 1번에서 정상적인 케이스를 전부 계산했기 때문에, 2, 3번에서는 예외 케이스만 계산해주면 된다.

 

즉, dp[N] = dp[N-2]*dp[N] + dp[N-4]*2 + dp[N-6]*2 ... 가 된다.