[Python] 타일 채우기 (백준 2133번)

🤔 문제

 

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

 

 

---

🔍 문제 풀이 과정

 

 

예전에 풀었던 2xn 타일링 문제와 비슷해서 바로 dp 문제라는 것을 떠올릴 수 있었습니다.

 

dp 테이블은 dp[n]이 3*n 크기의 벽을 채울 수 있는 경우의 수로 가정하고 만들었습니다.

 

규칙을 찾기 위해서 위의 그림처럼 하나씩 경우의 수를 그려가며 풀어보았습니다. 그 결과

• n=홀수 인 벽은 채울 수 없다.
• n=2인 경우에는 3가지 경우가 가능
• n=4인 경우부터는 기존의 조합을 사용하지 않는 2개의 새로운 경우와, 기존의 조합을 활용한 경우의 수가 존재한다.

라는 규칙을 찾았습니다. 조금 더 구체적으로 설명하면, n=4 이상일 때 가능한 경우의 수는 다음과 같습니다.

• 기존 경우의 수로 채우지 못하는 2가지 경우
• 먼저 2칸을 채우고 (=dp[2]), 남은 칸을 기존 경우의 수로 채우는 경우 (=dp[n-2])
• 먼저 4칸을 채우고 (=dp[4]), 남은 칸을 기존 경우의 수로 채우는 경우 (=dp[n-4])
• (반복)

식으로 나타내보면

# (n>=8일 때)
dp[n] = 2 + dp[2]*dp[n-2] + dp[4]*dp[n-4] + dp[6]*dp[n-6] + ...

 

위와 같이 표현할 수 있습니다.

이제 코드로 나타내보면 다음과 같이 풀 수 있습니다.

import sys

input = sys.stdin.readline

n = int(input())

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

dp[2] = 3

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

print(dp[n])

 

dp[2]만 특이하게 3가지 조합이 새로 생겨나기 때문에, 이 점을 고려해야 합니다.

 

 

---

📜 결과