[ 백준 2133 ] 타일 채우기 (C++)

백준의 타일채우기(2133) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

3 x N 크기의 벽을 2 x 1 , 1 x 2 타일들로만 채울 때, 그 경우의 수를 구해야 하는 문제이다.

작은 수들부터 차근차근 만들어보면서 하나의 규칙을 한번 찾아보자. 지금부터는 표현을 간단하게 하기 위해서 수식을

하나 사용해볼 것이다. F[A] = B 라는 수식을 사용할 것인데, 이 수식의 의미는 "3 x A크기의 벽을 2 x 1 , 1 x 2 타일들로만 채울 때, 채울 수 있는 경우의 수는 총 B개입니다." 를 의미한다.

먼저, N이 홀수인 경우를 생각해보자.

생각해볼 수 있는 가장 쉬운 예로 N = 1 을 생각해보자.

과연, 3 x 1 크기의 벽을, 2 x 1 , 1 x 2 타일들로만 채울수가 있을까 ?? 절대로 채울 수가 없다.

직접해보면 알겠지만, 3 x 3 , 3 x 5 ... 등등 3 x 홀수 크기의 벽은 1x2 , 2 x1 타일들로 채울 수가 없다.

따라서, 만약 주어진 입력값 N이 홀수라면, 그 즉시 바로 0을 return 시켜줘버리면 된다.

즉 ! F[홀수] = 0 이 된다.

그럼 N = 0 인 경우는 ? 입력으로 주어지지 않는다. 하지만 ! 그냥 이렇게 생각해보자. "존재하지 않는 벽을 2 x 1, 1 x 2 타일로 채우는 경우의 수는 ? 그 어떤 타일을 하나도 사용하지 않으면 채울 수 있습니다." 라고 ! 따라서 F[0] = 1이다 라고 !

위의 말에 너무 신경쓰지는 말고 그냥 문제 풀이에 넘어가보도록 하자.

그럼 ! 지금부터는 N이 짝수인 경우들을 알아보자.

가장 먼저 N = 2인 경우를 살펴보자.

3 x 2 크기의 벽을 2 x 1 , 1 x 2 타일로만 채워야 한다. 그럼 가능한 모든 경우를 그려보면 다음과 같이 3가지 경우가 존재한다.

.

이렇게 3가지 경우만이 존재한다. 크기가 별로 크지 않기 때문에 직접해봤더니 위와 같이 3가지 경우가 존재했다.

그런데 ! 지금부터는 위에 3가지 타일(3 x 2 를 채운 3개의 경우)들이 굉장히 많이 쓰이게 될 것이다.

그래서 본인이 쉽게 표현하기 위해서 A, B, C 라는 이름을 붙여주었다.

이제부터는 A타일 ~ , B타일 ~ , C타일 ~ 이라는 표현을 자주 사용할 것이니, A타일이 어떤 모양을 의미하는지, B타일이 어떤 모양을 의미하는지, C타일이 어떤 모양을 의미하는지 잘 인지하고 계속해서 진행해보자.

F[2] = 3

3 x 4 크기의 벽을 채워보자.

3 x 4 크기의 벽을 채울 때는, 쉽게 생각해서 "3 x 2 크기의 벽을 2번 채우는 형태" 라고 생각해볼 수 있다.

그런데 우리는 3 x 2 크기의 벽은 A, B, C 3가지 경우가 존재한다는 것을 이미 알고 있다.

그럼 ! A , B , C  3가지 벽돌들을 잘 조합해서 만들어보면 다음과 같이 9개의 경우가 발생한다.

.

3 x 4 크기의 벽을 3 x 2 크기의 벽 2개로 나눈다고 가정했을 때, 가장 첫 줄은 앞에 3 x 2 크기의 벽에 'A타일'이 들어간 형태이다. 두 번째 줄은 앞에 3 x 2 크기의 벽에 'B타일'이 들어간 형태이다. 마지막 줄은 'C타일'이 앞에 들어간 형태이다.

직접 해보지 않더라도, 3 x 2 크기의 벽을 만들 수 있는 경우의 수가 3가지이고, 이 3가지로 2번을 채워야 하는 형태이기 때문에 3 x 3 = 9 라는 것을 쉽게 알 수 있다.

그런데 ! 여기서부터 크나큰 문제가 하나 발생한다. 바로 ! 3 x 4 크기의 벽을 채울 수 있는 경우의 수가 9가지가 아니라는 것이다. 답부터 말하자면 11가지 이다. 우리가 확인하고 있지 못하는 2가지 경우가 더 존재한다는 것이다.

어떤 경우일까 ?? 위의 9가지 경우는 우리가 3 x 4 크기의 벽을 굉장히 단순하게 생각해서 3 x 4 를 3 x 2 + 3 x 2 의 형태로

나눈 후, 3 x 2를 채워가는 형식이었다. 그런데 나눠지지 않는 경우가 존재한다는 것이다.

.

바로 위의 그림과 같은 2가지 경우이다. 위의 2가지 모양은 우리가 기존에 계산했던 방식과 같이, 3 x 4를 3 x 2 크기의 벽 2개로 나눠서 계산할 수는 없는 형태를 가지고 있다. 그리고 마치 모양이, A, B, C타일들이 서로 엉켜있는(?) 듯한 모양을 가지고 있다. 그럼 지금부터는 위의 2가지 모양을 "특별한 모양" 이라고 표현하겠다. 다시 정리해서 이야기해보면, "특별한 모양"이라는 것은, 우리가 굉장히 단순하게 계산해서는 알 수 없는, 마치 A, B, C타일이 서로 엉켜있는 듯한 모양을 의미한다.

그럼 ! 여기서 한번 돌아가보자. 3 x 4 크기의 벽을 채울 때는 위와 같이 '특별한 모양'들이 존재했는데, 그렇다면, 3 x 2 크기의 도형에서는 그런 모양들이 존재하지 않았을까 ??

3 x 2 크기의 도형에는 이런 특별한 모양이 존재하지 않는다. 3 x 4 크기의 벽부터 '특별한 모양'들이 존재하게 된다.

F[4] = 11

이제 3 x 6 크기의 벽을 채워보자.

3 x 6크기 또한, 먼저 가장 단순하게 생각해보자.

3 x 6크기를 3 x 4 와 같이 2개의 벽으로 나눠보는 것이다.

1. 3 x 4 + 3 x 2 형태의 벽

2. 3 x 2 + 3 x 4 형태의 벽

이런식으로 한번 나눠서 계산을 해보자.

먼저 첫 번째 경우이다. 3 x 6을 다음 그림처럼 2개의 벽으로 나누는 것이다.

.

이런식으로 ! 그럼 위의 그림에서 발생할 수 있는 경우의 수는 너무나도 쉽게 계산할 수가 있다.

왜냐하면, 각각의 벽을 채우는 경우의 수를 적어보면 다음과 같기 때문이다.

.

우리는 이미 위에서 F[4]와 F[2]의 값 모두다 계산해 놓았다. F[4] = 11 , F[2] = 3 이기 때문에,

첫 번째 경우에서 발생할 수 있는 경우의 수는 33개 이다.

그럼 두 번째 경우로 넘어가자.  두 번째 경우는 다음과 같이 계산이 된다.

.

그렇기 때문에 F[2] = 3, F[4] = 11 이라는 것을 알고 있으므로, 채울 수 있는 경우의 수는 3 x 11 = 33 이 된다.

그럼 첫 번째 경우에서 33가지, 두 번째 경우에서 33가지, 현재까지 총 66가지 경우의 수로 채울 수 있음을 알 수 있다.

물론 ! 이 수치가 답은 아닐 것이다. 왜 ? 이놈도 "특별한 모양"을 가지고 있을 수 있기 때문이다.

그런데 ! 특별한 모양을 이야기하기 전에, 첫 번째 경우와, 두 번째 경우에 대해서 이야기를 조금만 더 해보자.

본인이 첫 번째 경우(3 x 4 + 3 x 2)에서 발생할 수 있는 조각들 중 하나를 가져와보겠다.

.

첫 번째 경우에서 발생할 수 있는 경우의 수 중 하나이다.

앞에 있는 3 x 4 크기의 벽을 'A타일 + A타일' 의 조합으로 채운 후에, 남은 3 x 2 크기의 벽을 'A타일'의 조합으로 채운 경우이다. 여기까지는 전혀 이상하거나 틀린 점이 없다.

그럼, 두 번째 경우(3 x 2 + 3 x 4)에서 발생할 수 있는 조각들 중 하나를 가져와 보겠다.

.

두 번째 경우에서 발생할 수 있는 경우의 수 중 하나이다.

앞에 있는 3 x 2 크기의 벽을 'A타일'로 채운 후에, 남은 3 x 4 크기의 벽을 'A타일 + A타일'의 조합으로 채운 경우이다.

잘못되거나 틀렸을까 ?? 아니다. 잘못되거나 틀리지 않았다. 그런데 뭔가 잘못되고 있다는 느낌이 올 것이다.

왜 ?? 우리는 첫 번째 경우(3 x 4 + 3 x 2)로 채울 때, 단순하게 F[4] * F[2] 를 통해서 계산을 하였다.

반대로 두 번째 경우(3 x 2 + 3 x 4 )로 채울 때에도, 단순하게 F[2] * F[4]를 통해서 계산을 하였다.

그래서 총 66가지라는 경우를 구했지만, 이 66가지 경우에는 위에서 가져온 하나의 예시와 같이, 중복되는 경우가 너무나도 많다는 것이다. 과연 중복되지 않는게 있을까 ?? 사실 거의없다. 왠만한 모양들이 다 중복된 모양일 것이다.

그래서 위에서처럼 간단하게 계산을 할 수가 없다.

그럼 지금부터는 초점을 한번 바꿔보자. 첫 번째 경우는 그대로 두고, 두 번째 경우를 조금 수정해보자.

두 번째 경우는 3 x 2 + 3 x 4 로 채우는 경우였는데, 과연 이렇게 채우면서 첫 번째 경우(3 x 4 + 3 x 2)와 중복되지 않는 모양은 뭐가 있을까 ?? 얼핏 생각해보면 어떻게 만들더라도 무조건 첫 번째 경우안에 다 속한 경우일 것 같다.. 그런데 !

여기서 "특별한 모양" 이 등장하게 된다.

첫 번째 경우, 즉, 3 x 6 크기의 벽을, 3 x 4 크기의 벽 + 3 x 2 크기의 벽으로 채우는 이 경우에, 하나의 특징을 이야기해보면, 가장 마지막 타일이 무조건 A혹은 B혹은 C타일로 끝난다는 것이다. 왜 ??

.

이런형태이기 때문에, 뒤에 F[2]에 들어올 수 있는 타일은 무조건 A타일, B타일, C타일밖에 없다는 것이다.

절대로 다른 타일로 저 3 x 2 를 채울 수는 없다. 한번 더 들어가서 왜 ? 3 x 2 를 채우는 경우는 A, B, C 밖에 없기 때문이다.

그럼, 다시 두 번째 경우로 들어와보자.

.

아까처럼 단순하게 F[2] * F[4]로 계산을 하게되면, 첫 번째 경우와 정말 많은 중복되는 경우들이 발생하게 된다.

근데 ! 이제는 구체적으로 이야기를 해보자. "정말 많은 중복되는 경우" 들이 어떤 경우들일까 ?? 바로, F[4]를 채울 때, 가장 마지막 3 x 2 크기의 벽을 A혹은 B혹은 C타일로 채워지는 모든 경우는 다 중복되는 경우일 것이다.

그렇다면 "중복되지 않는 경우"를 만들기 위해서는 어떻게 해야할까 ?? F[4]의 가장 마지막, 3 x 2 크기의 벽을, A혹은 B혹은 C타일로 채우지 않으면, 첫 번째 경우와는 중복되지 않는 경우를 만들 수 있을 것이다. 그런데 ? 분명히 위에서도 계속 언급했듯이, 3 x 2 크기의 벽은 무조건 A, B, C타일로만 채울 수 있다고 하지 않았나 ? 맞다. 하지만 우리가 지금 채워야 하는 것은 3 x 2가 아니라, 3 x 4 크기의 벽을 채우기만 하면 된다. 3 x 4 크기의 벽을 채울 때, 가장 마지막 3 x 2 크기의 벽을 A, B, C로만 채우지 않으면 된다. 어떤 경우가 있을까 ?? 바로 "3 x 4 크기의 벽을 채울 때 만들어 졌던 특별한 모양을 넣는 경우" 이다.

.

하나의 예시이다. 3 x 6크기의 벽을 채울 때, 앞에 3 x 2는 A, B, C 중 하나로 채웠지만, 가장 마지막 3 x 2 크기의 벽을 A도 B도 C도 사용하지 않은 경우이다. 과연 이 경우가 첫 번째 경우에 존재할까 ?? 절대로 존재할 수가 없다.

따라서, 우리가 지금까지 이야기한 두번째 경우, 즉, 3 x 6 크기의 벽을, 3 x 2 + 3 x 4 크기의 벽으로 나눠서 채우는 계산을 진행했을 때, 단순하게 F[2] * F[4]를 한다면, 이는 첫 번째 경우와 굉장히 많은 경우들이 중복되어 계산되어지므로 올바른 계산이라고 할 수 없다. 3 x 2 + 3 x 4 크기의 벽으로 나눈다면, 이 때는, 중복을 피하기 위해서 F[2] * 2 가 된다.

F[2] * 2에서 '2'의 의미는 "3 x 4 크기의 벽을 채울 때 발생했던 특별한 모양 2가지를 의미" 한다.

그럼 다시 계산해보면, 첫 번째 경우에서 F[4] * F[2] = 33 으로 33가지가 발생하고,

두 번째 경우에서 F[2] * 2 = 6으로 현재까지 총 33 + 6 = 39가지가 발생하게 된다.

물론 ! 여기서도 특별한 모양 2가지가 존재한다. 본인은 N 값이 커질수록, 더 많은 특별한 모양들이 존재하는지 고민하고 그려봤지만, 어떤 경우에도 특별한 모양들은 "딱 2가지씩만" 존재한다.

.

N = 6일 때, 발생할 수 있는 특별한 모양 2가지이다.

따라서 N = 6을 채울 수 있는 경우의 수는 33 + 6 + 2 = 41 가지가 된다.

F[6] = 41.

그럼 ! 마지막으로 N = 8인 경우를 한번만 더 해보자.

위에서 했던대로 역시나 나눠서 계산을 해보자. 이제는 중복되는 경우까지 다 생각을 하면서 계산을 해보자.

Case1 : 3x8크기의 벽을 3x6 + 3x2 크기로 채우는 경우

Case2 : 3x8크기의 벽을 3x4 + 3x4 크기로 채우는 경우

Case3 : 3x8크기의 벽을 3x2 + 3x6 크기로 채우는 경우

Case1은 단순하게 F[6] * F[2]로 구할 수가 있다. Case1 = F[6] * F[2] = 41 * 3 = 123.

Case2부터는 중복을 생각해봐야 한다. Case1과의 중복을 피하기 위해서는 ? 가장 마지막 3 x 2 크기를 A, B, C로 채우지만 않으면 된다. 그럼 3 x 4 크기의 벽을 채울 때, 가장 마지막 3 x 2크기의 벽을 A, B, C로 채우지 않는 경우는 ? 특별한 모양을 사용하는 방법밖에 없다.

따라서 Case2에서 발생할 수 있는 경우의 수는 F[4] * 2(3x4를 채우는 특별한 모양 2가지) = 11 * 2 = 22 가 된다.

Case3또한 중복을 생각해 주어야 한다. Case3에서는 Case1, Case2와의 중복된 모양을 피해주어야 한다.

그럼 ? Case1과 중복되지 않기 위해서, 가장 마지막 3 x 2 크기의 타일을 A, B, C를 사용하면 안되고,

Case2와 중복되지 않기 위해서, 가장 마지막 3 x 4 크기의 타일을 "3 x 4 타일을 채울 때 발생한 특별한 모양" 을 사용하면 안된다. 위의 2가지 조건을 모두 만족하면, Case1과도, Case2와도 중복되지 않는 모양을 만들 수 있을 것이다.

어떤 모양이 있을까 ? 바로 3 x 6을 채우는 특별한 모양 2가지로 3 x 6을 채워주면 된다.

즉 ! Case3에서는 F[2] * 2(3 x 6을 채우는 특별한 모양 2가지) = 6 가지가 된다.

그리고 ! 최종적으로 3 x 8 을 채우는 특별한 모양 2가지 까지 추가한다면 전체 경우의 수가 나오게 된다.

F[8] = Case1 + Case2 + Case3 + 2 = 123 + 22 + 6 + 2 = 153 이 되는 것이다.

그럼 이제부터는 이를 구현하기 위해서, 보다 일반화된 식들로 계산을 해보자.

F[8]을 계산하기 위해서 우리가 계산한 값들을 모두 풀어서 적어보겠다.

F[8] = ( F[6] * F[2] ) + ( F[4] * 2 ) + ( F[2] * 2 ) + 2

첫 번째 괄호는 Case1을, 두 번째 괄호는 Case2를, 세 번째 괄호는 Case3을, 가장 마지막 + 2는 특별한 모양 2개를 의미한다.

그런데 위의 식에서 '+2'라는 숫자를 이렇게 바꿔서 표현해보자.

F[8] = ( F[6] * F[2] ) + ( F[4] * 2 ) + ( F[2] * 2 ) + ( F[0] * 2 )

F[0] 이 어디서 나왔을까 ?? 사실 이 글의 가장 처음에 본인이 정말 짧게 설명하고 넘어온 것이다.

사실 N은 1 이상만 주어지기 때문에 N = 0인 경우는 문제에서 주어지지 않는다. 하지만, 우리가 초기식으로 F[0] = 1 이라고 설정을 해놓는다면 ? 단순 '+ 2' 라는 문구를 F[0] * 2 라는 문구로 바꿔서 표현할 수도 있다.

그럼 이제 위의 식에서 '8'이라는 숫자를 'N'으로 바꿔서 적어보자.

F[N] = ( F[N - 2] * F[2] ) + ( F[N - 4] * 2 ) + ( F[N - 6] * 2) + ( F[N - 8] * 2 ) + ... + ( F[0] * 2 )

이것이 바로 이 문제의 점화식이다.

이 식을 이용해서 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 35
using namespace std;
 
int N;
int DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    if (N % 2 == 1)
    {
        cout << 0 << endl;
        return;
    }
    DP[0] = 1;
    DP[1] = 0;
    DP[2] = 3;
    for (int i = 4; i <= N; i = i + 2)
    {
        DP[i] = DP[i - 2] * DP[2];
        for (int j = i - 4; j >= 0; j = j - 2)
        {
            DP[i] = DP[i] + (DP[j] * 2);
        }
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}