[BOJ] 2133 - 타일 채우기

[BOJ] 2133 - 타일 채우기

문제

문제

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

입력

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

출력

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

예제 입력

2

예제 출력

3

문제 해결

3xn 크기 벽을 채우는 것이다. 준비된 타일은 2x1 타일 이고, 따라서 (n==홀)수 일때의 경우의 수는 0인것을 알 수 있다.

그럼 이제 n 이 짝수일때 경우의 수를 따져보자.

2인 경우애는 총 3개이다.

12  11  11
12  22  23
33  33  23

그럼 4개인 경우에는 2인 경우에 2개를 붙인 경우이므로 3 * 3 에다가 3x4을 만들 수 있는 경우 2가지가 추가된다.

1122 1224
3446 1334
3556 5566

따라서 총 11가지이다.

그럼 6개일때는 위 과정과 똑같이 2인 경우 * 3x4 경우 + 4인 경우 3x2 경우 에 3x6을 만들 수 있는 케이스가 존재한다.

따라서 n의 경우의 수는 n까지의 짝수의 경우의 수 * 특정 3xn 블럭을 만들수 있는 경우의 수
n 이 2일때는 3개, 나머지는 2개 + n 단계에서 특별하게 만들 수 있는 2가지 경우를 더한 값이 된다.

python 코드

n = int(input())
dp = [0] * (n+1)

for i in range(1, n+1):
    if i % 2 == 1 :
        dp[i] = 0
    elif i == 2 :
        dp[i] = 3
    else :
        temp = 0
        for j in range(2, i-1):
            if j == i-2 :
                temp += dp[j] * 3
            elif j % 2 == 0 :
                temp += dp[j] * 2
        dp[i] = temp + 2

print(dp[n])

Test case

n=2 3
n=3 0
n=4 11
n=5 0
n=6 41
n=7 0
n=8 153

느낀점

특정 케이스에서 어떤 수 가 추가된다는 것을 인지하지 못하여 조금 오래 걸렸던 문제이다.