백준 11333번: 4×n 타일링

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

11333번: 4×n 타일링

---

이 문제는 원래는 정석적인 도미노 타일링 문제가 아니어서 손을 안 대려 했습니다.

 

그런데 호기심에 다른 블로그 풀이들을 서치해보니까 profiling을 이용해서 딱히 선형점화식 없이 풀더라고요.

 

물론 그것들도 좋은 풀이인데 저는 선형점화식을 찾아보고 싶었습니다.

 

(참고로, 이 문제가 딱히 [BOJ11726] 2xn타일링에서 유래했다고 보긴 어려울 것 같습니다.

물론 문제 상황은 비슷하지만, 점화식의 형태나 유도과정이 다소 다르다고 생각합니다.

개인적으로 그보다는, [BOJ13976] 타일 채우기 2 혹은 [BOJ2133], 혹은 [BOJ2718]가 더 유사하다고 생각합니다.

점화식을 유도하고, 후술하겠습니다.)

 

---

일단 점화식을 유도하는 방법론에 대해서, 저는 $4 \times 3N$ 타일링을 왼쪽부터 오른쪽으로 진행하며 가장 왼쪽에

 

$4 \times 3K$의 basic blocks을 배치하고, 나머지 $4 \times 3(N-K)$ 의 면적은 부분문제로 설정할 것입니다.

 

이렇게 되면 만약 $1 \times 3$의 tromino로 타일링할 수 있는 basic blocks의 가로 길이의 상한이 존재하여 $3P$라면

 

다음 점화식을 얻게 됩니다.

 

$$ A_{3n} = \sum_{i=1}^{P} B_{3i} \times A_{3(n-i)} $$

 

식에서 $\left \{ A_{3k} \right \}$은 $4 \times 3k$ 타일링의 경우의 수, $\left \{ B_{3k} \right \}$은 $4 \times 3k$의 basic blocks의 개수입니다.

 

또한, 이후의 편의를 위해 $A_{0}=1$로 정의합니다.

 

이제 $\left \{ B_{3k} \right \}$의 초기 몇 개의 값을 구해서, 그 사이의 규칙을 찾아보겠습니다.

 

OEIS를 참고하면, 다음 테이블을 얻을 수 있습니다. ( https://oeis.org/A049086 )

 

k	$A_{3k}$
0	1
1	3
2	13
3	57
4	249
5	1087

 

이를 통하여 다음을 확인할 수 있습니다.

 

$$13 = 3 \times 3 + 4$$

 

$$57 = 13 \times 3 + 3 \times 4 + 6$$

 

$$249 = 57 \times 3 + 13 \times 4 + 3 \times 6 + 8$$

 

$$1087 = 249 \times 3 + 57 \times 4 + 13 \times 6 + 3 \times 8 + 10$$

 

따라서, $k>1$에 대하여, 다음이 성립함을 관찰할 수 있습니다.

 

$$ B_{3k+3} = B_{3k} + 2 $$

 

그런데 $ \left \{ B_{3k} \right \}$ 은 유한수열일까요? $4 \times 6$까지만 그려봐도, 또 규칙을 보더라도, 무한수열같아보입니다.

 

일단은 무한수열로 가정하고 점화식을 도출해보겠습니다.

(참고로, 이 단계의 식을 그대로 문제에 적용하면 $O(n^{2})$이므로 이 문제에서 적합한 식인지는 애매합니다.)

 

$$ A_{3n} = 3A_{3n-3} + 4A_{3n-6} + 6A_{3n-9} + 8A_{3n-12} + \cdots + (2n-2)A_{3} + 2n $$

 

이제 이 수열을 변형하여, 앞서 인용했던 oeis의 깔끔한 식을 유도해보겠습니다. 우선 다음 식은 위 식의 따름입니다.

 

$$ A_{3n+3} = 3A_{3n} + 4A_{3n-3} + 6A_{3n-6} + 8A_{3n-9} + \cdots + 2nA_{3} + (2n+2) $$

 

따라서, 다음을 알 수 있습니다.

 

$$ A_{3n+3} = 4A_{3n} + A_{3n-3} + 2(A_{3n-6} + A_{3n-9} + \cdots + A_{3} + 1) $$

 

여기서 같은 과정을 거칩니다.

 

$$ A_{3n+6} = 4A_{3n+3} + A_{3n} + 2(A_{3n-3} + A_{3n-6} + \cdots + A_{3} + 1) $$

 

한 번 더, 아래에서 위를 뺍니다.

 

$$ A_{3n+6} = 5A_{3n+3} - 3A_{3n} + A_{3n-3} $$

 

이는 math stackexchange, oeis, 기타 블로그 등에서 사용한 식과 동치임을 확인할 수 있습니다.

 

이에 따라 구현하면 문제는 쉽게 해결됩니다.

 

물론, 이대로는 $O(n)$에 해결하는 것이므로, 점화식을 행렬 형태로 바꾸는 것도 좋습니다.

(그 경우 일반적으로 가로 길이가 $N \leq 10^{18}$ 수준이라도 쉽게 커버할 수 있습니다.)

 

행렬 형태의 점화식은 다음과 같습니다.

 

$$ \begin{bmatrix} A_{3n+6} \\ A_{3n+3} \\ A_{3n} \end{bmatrix} = \begin{bmatrix} 5 & -3 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} A_{3n+3} \\ A_{3n} \\ A_{3n-3} \end{bmatrix} $$

 

단, 공통적으로 주의해야 하는 것은, 이 문제에서는 가로 길이가 3의 배수가 아닌 경우도 있다는 것입니다.

 

제 코드는 다음과 같습니다.

 

/*
 * Author : thdtjdals3
 * Date : 2022-05-01
 * Description : BOJ 11333
 * Link : https://www.acmicpc.net/problem/11333
 */

#include <stdio.h>
#define mod 1000000007

typedef struct {
	unsigned long long array[3][3];
} Matrix;

Matrix matrix_multiply_modular(Matrix A, Matrix B);
Matrix matrix_power_modular(Matrix A, int power);

int simple[] = {1, 3, 13};

int main() {
	
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int N;
		scanf("%d", &N);
		
		if (N % 3) {
			printf("0\n");
			continue;
		}
		
		if (N <= 6)	{
			printf("%d\n", simple[N / 3]); // 3, 6
			continue;
		}
		
		Matrix Base =
		{{
			{5, mod - 3, 1},
			{1, 0, 0},
			{0, 1, 0}
		}};
		Base = matrix_power_modular(Base, (N - 6) / 3);
		
		long long Answer =
		(Base.array[0][0] * simple[2]
		+ Base.array[0][1] * simple[1]
		+ Base.array[0][2] * simple[0]) % mod;
		printf("%lld\n", Answer);
	}
	return 0;
}

Matrix matrix_multiply_modular(Matrix A, Matrix B)
{
	Matrix result = {{{}}};
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				result.array[i][j] += A.array[i][k] * B.array[k][j];
			}
			result.array[i][j] %= mod;
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, int power)
{
	Matrix result =
	{{
		{1, 0, 0},
		{0, 1, 0},
		{0, 0, 1}
	}};
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular(result, A);
		}
		A = matrix_multiply_modular(A, A);
		power /= 2;
	}
	return result;
}

(C11, 0ms, 1116KB, 제출번호 42714964)

---

[BOJ11726]의 경우, 사실상 타일링이라는 점 외엔 공통분모가 없습니다. 게다가 널리 알려진 풀이의 대부분은, 타일링을 basic blocks + subproblem이 아니라, subproblem을 expand하는 방법입니다. 따라서 직사각형의 크기도, 블럭의 크기도, 방법론도, 점화식의 유도과정에 대한 복잡함도, 모두 다른 문제라고 할 수 있을 것입니다.

 

[BOJ2718]의 경우, 우선 채워야 하는 직사각형의 크기가 비슷하며, basic blocks의 개수에 관한 규칙이 존재하긴 한다는 점에서 [BOJ11726]보단 낫다고 할 수 있습니다. 다만 이 문제는 가로 길이도 지나치게 작고, 도미노를 사용하는 타일링이며, basic blocks 개수에 관한 규칙은 상당히 다릅니다. 그래서 아주 연관있는 문제는 아닙니다.

 

[BOJ13976]의 경우, 사실상 이 문제의 열화판으로 볼 수 있습니다. 우선, [BOJ13976]은 $1 \times 2$ 도미노로 $3 \times N$ 공간을 타일링합니다. [BOJ11333]의 경우, $1 \times 3$ 트로미노로 $4 \times N$ 공간을 타일링합니다. 이 부분이 저는 매우 analogous하다고 느꼈습니다.

 

게다가 [BOJ13976]도 점화식의 크기가 $N$에 비례해서, 적절히 차수를 줄이며 서서히 $O(\log N)$까지 복잡도를 줄이고 있습니다. 이 과정도 매우 비슷한 편입니다. 다만, [BOJ11333]은 중간 공정을 한 번 더 거치긴 했지요. 그래서 그런지, 결과적으로 [BOJ13976]에서 나타난 $2 \times 2$의 transfer matrix가 여기서는 $3 \times 3$으로 바뀌었습니다.

 

(별개의 얘긴데, 프로그래머스에 [BOJ11726]과 [BOJ13976](의 열화판)이 존재해서 구글 검색해서 나온 풀이가 비슷한 방향으로 도배되었네요.)