[백준 2133] 타일 채우기

문제

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

 

입력

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

출력

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

---

풀이

점화식을 세우기 위해 손으로 그려보았다

2*1, 1*2칸을 사용하여 3*N칸을 채우는 것이기에 N이 홀수인 경우에는 경우의 수가 0이 나온다

N=2 인 경우 3가지 경우의 수가 나온다

N=4 인 경우, N=2 인 경우를 두번 곱하고 4칸을 채울 수 있는 다른 모양이 2개 존재하여 3*3+2=11이 나온다

 

여기까지만 구해보고 점화식을 세운 결과 4칸을 채우는 모양까지 고려한다면 dp[n-4]에 2를 곱하여 더해야 하기에

dp[i] = dp[i-2]*3 + dp[i-4]*2

하지만 제출 결과는 틀리다고 말한다

 

놓치고 있는 패턴이 있는 것 같아서 꽤 오랜 시간을 생각했다

결과적으로 4칸을 채울 수 있는 2가지 패턴은 4칸만 채울 수 있는게 아니라 4칸, 6칸, 8칸, 10칸 ... 즉, dp[i-4]부터 2씩 감소하며 2가지의 경우의 수를 추가로 부여할 수 있었다

수정된 점화식은

dp[n] = dp[n-2]*3 + sum(dp[n-j]*2) + 2  ( n이 짝수 일 경우, 4 <= j <= n, j는 2씩 증가)

마지막으로 더해지는 2는 dp[2]의 패턴이 들어가지 않는 2가지 패턴을 더해준 것이다

if N>=2:    # N이 2인 경우
    dp[2] = 3
if N>=4:    # N이 4인 경우
    dp[4] = dp[2]*3+2

for i in range(6,N+1):
    if i%2==0:  # 홀수는 모두 0
        dp[i] += dp[i-2]*3  # dp[2]를 dp[n-2]에 곱하여 더해줌
        for j in range(i-4,-1,-2):  # i-4부터 2씩 감소하며 특수패턴 2가지를 곱하여 더해줌
            dp[i] += dp[j]*2
        dp[i]+=2 # dp[2] 패턴이 없는 특수한 패턴 2가지 더해줌