[Python] BOJ / 2133번 / 타일 채우기

2133번: 타일 채우기

 

📝 문제

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

 

📜 풀이

• 기본적으로 n이 홀수인 경우는 타일을 모두 채울 수 없음
• n = 2부터 시작하여 벽의 크기가 2씩 증가할 때마다 새로운 모양으로 벽을 채우는 경우가 2씩 늘어남
• 따라서 다음과 같은 규칙이 성립됨
  • n = 2일 때의 경우의 수는 3가지
  • n = 4일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 2일 때의 경우의 수) + 2
  • n = 6일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 4일 때의 경우의 수) + 2
  • n = 8일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 6일 때의 경우의 수) + 2
• 이를 점화식으로 나타내면 다음과 같음
  • dp[i] = dp[2] * dp[i - 2] + 2
• 추가로, n의 크기가 6이상인 경우부터는 새로운 모양을 포함해서 벽을 채우는 경우를 고려해야하므로 아래와 같은 식을 세울 수 있음
  • dp[i] += dp[i - j] * 2
  • 즉, n = 4인 경우부터는 새로운 모양이 2개씩 추가되므로 벽을 새로운 모양으로 채우고 남은 부분을 채우는 경우의 수에 x2를 해주는 것

 

💻 소스코드

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

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