[백준 BOJ] 2133 타일 채우기 (python)

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

2133번: 타일 채우기

 

🔥 작성 코드

N = int(input())

if N%2:
    result = 0
else:
    dp = [0] * (N+1)
    dp[2] = 3
    for i in range(4, N+1, 2):
        dp[i] = 3*dp[i-2] + 2
        if i != 4:
            for j in range(4, i-1, 2):
                dp[i] += 2*dp[j-2]

    result = dp[N]

print(result)

⭕ 해설

1. N이 홀수라면 3xN의 벽은 크기가 홀수가 됩니다. 따라서 2x1, 1x2 크기의 타일로 채울 수 없습니다.
2. N이 짝수일 경우 2부터 차근차근 생각해봅니다.
   • 3x2 크기의 벽은 채울 수 있는 경우의 수가 3가지입니다.
3.  N이 4는 N은 2일 때 만들 수 있는 벽을 두 개 붙이면 가능합니다.
   
   • 그리고 새로운 모양의 타일이 2개 추가됩니다.
   • 새로운 모양의 타일은 4 이후로(6, 8, 10, ...) 항상 2개씩 추가됩니다.
4. N이 6일때는 4로 만드는 벽뒤에 2로 만드는 벽을 붙이면 가능합니다.
   • 4에서 새로 만들어진 타일의 앞에 2로 만드는 타일을 붙이는 경우도 더해줍니다.
   • 마찬가지로 새로운 모양의 타일 2개가 추가됩니다.
5. N이 8일때는 6으로 만드는 벽뒤에 2로 만드는 벽을 붙입니다.
   • 마찬가지로 6에서 새로 만들어진 타일의 앞에 2로 만드는 타일을 붙이는 경우도 더해줍니다.
   • 4에서 새로 만들어진 타일 앞에 4로 만드는 타일을 붙이는 경우도 더해줍니다.
   • 새로운 모양 타일 2개를 추가합니다.
6. 이런식으로 주어지는 N까지 구해줍니다.
   • 앞의 내용을 바탕으로 4 이상의 i번 째 경우의 수는 다음과 같이 구할 수 있습니다. 
   • 이 전까지 구한 경우의 수 x 3 (i-1에서 만들 수 있는 경우 뒤에 2로 만드는 타일을 붙임)
   • i-2로 만드는 경우의 수 x 2 (i-2에서 만들 수 있는 경우 앞에 4에서 새로 만든 타일을 붙임)
   • i-4로 만드는 경우의 수 x 2 (i-2에서 만들 수 있는 경우 앞에 6에서 새로 만든 타일을 붙임)
   • ,,,
   • 2로 만드는 경우의 수 x 2 (2로 만드는 경우 앞에 i-1에서 새로 만든 타일을 붙임)
   • i에서 새로 만들어지는 타일 2개
   • 모두 더해주면 i번째 타일의 경우의 수가 됩니다.
   • 이해하기 어려우면 j의 범위를 다음과 같이 수정해도 됩니다.

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