[C/C++] 백준 #2133 타일 채우기(동적 계획법)

#2133 타일 채우기 문제는 동적 계획법을 이용해서 풀 수가 있습니다.  하지만 원리만 알면 조금 더 쉬운 방법으로도 해결할 수가 있습니다.

 

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

2133번: 타일 채우기

 

문제는 3xn 공간을 2x1 타일로 채우는 경우의 수를 구하라는 문제입니다.  아주 간단하지만 n이 홀수인 경우에는 채울 수 있는 방법이 없습니다.  n이 짝수인 경우에만 채울 수 있는 경우가 발생하죠.

 

3xn 공간 타일링 예

저는 동적 프로그래밍을 하기 위해서 다음과 같은 경우를 생각했습니다.  마지막 칸에 나올 수 있는 패턴들입니다.  마지막 칸의 패턴은 아무것도 없는 상태, 맨 위에만 한칸 채워진 상태, 맨 위에 두개만 두칸 채워진 상태, 맨 아래만 한칸 채워진 상태, 맨 아래 두칸만 채워진 상태, 그리고 세칸 모두 채워진 상태로 보았습니다.

 

이럴 경우 우리가 패턴마다 갈 수 있는 패턴을 구하고, 마지막에는 모두 채워진 패턴의 개수를 구하면 경우의 수를 동적 계획법으로 구할 수 있습니다.

 

pattern	nextt pattern
000	001, 100, 111
001	000, 110
100	000, 011
011	100
110	001
111	000

 

이렇게 해서 패턴을 만들 수 있습니다.  저는 이것을 이용해서 프로그램을 작성했지만, n이 홀수인 경우에는 경우의 수가 0이라는 점을 이용하면 다음과 같이 할 수가 있습니다.  나올 수 있는 패턴은 000, 011, 110 뿐입니다.  그런데 이것을 모두 직접 수기로 시뮬레이션하기는 꽤 귀찮습니다.  프로그램을 통해서 찾게 되면, 최종적으로 다음과 같은 결과를 얻을 수 있습니다.

 

\[ T(0) = 1, T(2) = 3 \]

\[ T(2n) = 4T(2n-2) - T(2n-4) \]

 

이 식에 따르면 n = 4 일때, 11, n = 5 일때, 41의 값을 찾을 수 있습니다.  이 방법을 이용하면 일반항은 다음과 같이 됩니다.

 

\[ T(2n) = \frac{1}{2 \sqrt{3}}((\sqrt{3}+1)(2+\sqrt{3})^n +(\sqrt{3}-1)(2-\sqrt{3})^n) \]

 

일반항을 구해서 하는 방법은 좋긴 하지만, 정밀도가 떨어지기 때문에 적절한 반올림을 통하면 됩니다.  어차피 이 문제는 \(O(n)\) 알고리즘이기때문에 작은 n에 대해서는 다른 방법을 생각하지 않아도 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2133
//        - by Aubrey Choi
//        - created at 2019-09-12
//------------------------------------------------
#include <stdio.h>

//    000, 001, 100, 011, 110, 111
int main()
{
    int n;
    scanf("%d", &n);
    if(n&1) { puts("0"); return 0; }
    int dp[31][6];
    dp[0][0]=1, dp[0][1]=0, dp[0][2]=0, dp[0][3]=0, dp[0][4]=0, dp[0][5]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][1]+dp[i-1][2]+dp[i-1][5];
        dp[i][1]=dp[i-1][0]+dp[i-1][4];
        dp[i][2]=dp[i-1][0]+dp[i-1][3];
        dp[i][3]=dp[i-1][2];
        dp[i][4]=dp[i-1][1];
        dp[i][5]=dp[i-1][0];
    }
    printf("%d\n", dp[n][0]);
}