[ 프로그래머스 3xn 타일링 (Lv4) ] (C++)

프로그래머스의 3xn타일링(Lv4) 문제이다.

[ 문제풀이 ]

가로 길이가 n이고 세로 길이가 3일 때, 3 x n 으로 이루어진 직사각형을 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의

타일로 가득 채울 때, 가능한 경우의 수를 구해야 하는 문제이다.

먼저 어떠한 규칙이 있는지 부터 알아보자.

먼저 n = 1 일 경우를 생각해보자.

3 x 1 의 형태를 띄고 있는 직사각형을 2 x 1 직사각형으로 채워야 한다. 어떻게 채워야할까 ?? 절대로 채울 수가 없다.

그럼 n = 2 를 넘겨두고, n = 3 인 경우를 생각해보자.

3 x 3 크기의 직사각형을 2 x 1의 직사각형으로 채워야 한다. 어떻게 채워야 할까 ?? 절대로 채울 수가 없다.

왜냐하면, 3 x 3 에는 3 x 1의 직사각형이 항상 남기 때문이다.

3 x 3를 채우기 위해서 노력해본 하나의 예시이다.

.

위와 같은 형태를 보게 되면 3 x 2 까지는 채워봤는데, 결국 3 x 1크기의 직사각형(빨강색 테두리)이 남게 된다.

그리고 우리는 3 x 1 크기의 직사각형은 2 x 1 타일로 절대 채울 수 없다는 것을 알고 있다. 따라서 ! 3 x 3 또한 채울 수 없게 된다.

마찬가지로, 그 이후에 나오는 모든 홀수들은 2 x 1 타일로 채울 수가 없다. 왜냐하면 위와 같은 상황처럼 '3 x 1'타일의 크기만큼

항상 공간이 남기 때문이다. 따라서 ! n 값이 홀수라면 그대로 0을 return 시켜버리면 된다. 홀수는 채울 수가 없다 !

그럼 이제부터 짝수를 알아보자. n = 2 인 경우를 알아보자.

n = 2일 경우에는 다음과 같은 형태로 직사각형을 채울 수 있다.

.

위와 같이 3가지의 방법으로 직사각형을 채울 수 있게 된다. 우리는 간단하게 여기서 하나만 체크 하고 넘어가보자.

"n = 2 일 경우에는 경우의 수가 3가지가 존재한다 !"

그럼 n = 4 일 경우를 알아보자. 이번에는 하나하나 그림으로 다 그려보지 말고 계산으로 한번 구해보자.

.

위의 그림은 3 x 4 크기의 직사각형을 본인이 2개의 직사각형으로 나눠보았다. 바로 3 x 2 짜리 사각형 2개이다.

빨강색 테두리도 3 x 2 짜리 사각형 , 파랑색 테두리도 3 x 2 짜리 사각형이다.

그럼 경우의 수가 몇 가지일까 ??? 우리는 위에서 3 x 2 짜리 사각형을 채우는 경우의 수는 총 3가지가 있다고 구해놓았다.

즉 ! 위의 빨강색 사각형을 채우는 경우의 수도 3가지, 파랑색 사각형을 채우는 경우의 수도 3가지가 존재할 것이다.

따라서 총 경우의 수는 3 x 3 으로 9가지가 될 것이다.

하지만 ! 여기서 계산이 끝나지가 않는다. n = 4일 때의 정답은 11가지 이다. 그럼 나머지 2가지 경우는 어떻게 발생할까 ??

.

바로 위와 같이 3 x 2 를 채울 때는 알지 못했던 '새로운 모양' 2가지가 더 추가된다. 그래서 n = 4 일 때의 값은 3 x 3 + 2 = 11 이 된다. 지금부터 위의 2가지 모양을 "조금 이상한 모양" 이라고 표현해보자. "n = 4 일 때부터는 '조금 이상한 모양' 2가지가 추가적으로 발생한다. ! "

n = 6 일 때를 보자. n = 6일 때는 그림을 한번 나눠서 생각해보자.

1. n = 4 인 사각형 + n = 2 인 사각형

2. n = 2 인 사각형 + n = 4 인 사각형

3. n = 6 인 사각형

이렇게 크게 3가지의 형태로 나누어진 그림으로 이야기 할 수 있다.

첫 번째 경우를 보자. n = 4인 사각형 + n = 2 인 사각형의 형태로 존재하는 n = 6인 사각형이다.

이 경우에는 n = 4인 사각형을 채우는데 드는 경우의 수 x n = 2인 사각형을 채우는데 드는 경우의 수 로 구할 수가 있다.

두 번째 경우를 보자. n = 2인 사각형 + n = 4인 사각형의 형태로 존재하는 n = 6인 사각형이다.

이 경우를 n = 2인 사각형을 채우는데 드는 경우의 수 x n = 4인 사각형을 채우는데 드는 경우의 수로 구할 수 있을까 ??

첫 번째 경우에서 n = 4인 사각형에 "조금 이상한 모양"이 아닌 3 x 2 짜리 2개로 구성되어 있는 경우를 생각해보자.

다시 말해서, 첫 번째 경우 3 x 4 짜리 사각형을 먼저 계산하고, 3 x 2 짜리 사각형을 계산해서 두 경우를 곱한걸로 결론을 냈던 경우에서, 3 x 4 짜리 사각형에 "조금 이상한 모양"이 아닌 사각형들로 이루어진 경우를 생각해보자.

즉 ! 3 x 2 짜리 직사각형 3개로 3 x 6을 채운 경우가 될 것이다. 지금 이 이야기를 왜 하고 있을까 ??

바로 n = 2 인 사각형 + n = 4인 사각형을 구할 때, 단순히, 이 두 경우를 곱해버려서 경우의 수를 계산하면 첫 번째 경우와 똑같은 경우가 중복되서 계산이 될 수 있다라는 것이다.

즉 ! n = 2 인 사각형 + n = 4 인 사각형에서는 n = 4가 "조금 이상한 모양"의 형태로 존재하는 경우만 계산을 해주면 된다.

지금부터 수식을 쓰면서 계산을 해보자. F[N] 을 "3 x N 타일을 채울 수 있는 경우의 수" 라고 정의하겠다.

F[2] = 3 이였고, F[4] = F[2] * F[2] + 2("조금 이상한 모양") = 11 이였다.

F[6]은 어떻게 될까 ??

첫 번째 경우에 의해서 F[4] * F[2] = 11 * 3 = 33

두 번째 경우에 의해서 F[2] * 2("조금 이상한 모양") = 6

세 번째 경우에 의해서 N = 6일 때 발생할 수 있는 "조금 이상한 모양" 2개를 더해서 결과적으로 33 + 6 + 2 = 41이 된다.

그래서 F[6]의 값은 41이 된다.

N = 8일 한 가지만 더 간단하게 계산해보자. N = 8은 다음과 같이 경우를 나눌 수 있다.

.

즉 ! F[8] = ( F[6] * F[2] ) + ( F[4] * 2 ) + ( F[2] * 2 ) + 2(N =8에서 발생할 수 있는 "조금 이상한 모양" 2가지)

이렇게 계산을 할 수 있다.

이제 이를 일반화 시켜보자.

F[N] = F[N - 2] * F[2] + F[N - 4] * 2 + F[N - 6] * 2 + ... + F[2] * 2 + 2 로 식을 세울 수 있다.

위의 점화식을 그대로 코드에 적용시켜 해결하였다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MODULER 1000000007
using namespace std;
 
int solution(int n) 
{
    if(n % 2 == 1) return 0;
    long long DP[5010] = { 0, };
    DP[0] = 1;
    DP[2] = 3;
    for(int i = 4; i <= n ; i = i + 2)
    {
        DP[i] = DP[i - 2] * 3;
        for(int j = i - 4; j >= 0 ; j = j - 2)
        {
            DP[i] = DP[i] + DP[j] * 2;
        }
        DP[i] = DP[i] % MODULER;
    }
    
   return (int)DP[n];
}

.