백준 27318번: 세상에서 가장 달달한 디저트 만들기 (matrix)

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

27318번: 세상에서 가장 달달한 디저트 만들기

---

문제에서는 $N$과 $M$이 달라질 때마다 완전히 꽉 차있는 $\left ( N^{M} \right )^{3}$짜리 정육면체로부터 시작하지만, 어차피 최종 결과물은 $N,M$값에 상관없이 부피 1짜리 정육면체들로 이루어져있습니다. 즉, $N$을 고정시킨 뒤, $M$을 하나씩 늘리며 이전 단계의 로쿰이 몇 번 나타나는지 확인하는 게 떠올리기 쉬운 풀이 같습니다.

 

그림으로 주어진 $N=4$, $M \leq 2$에서 생각해보겠습니다.

 

$M=2$일 때의 최종 결과물에서 $M=1$일 때의 로쿰이 나타나는 횟수는, 각 꼭짓점에서 $1$번, 그리고 각 모서리에서 꼭짓점 부분을 제외한 $N-2$번입니다. 따라서, 그 횟수는 $12N-16$입니다. 그리고 $M=3$일 때의 결과물에서는 $M=2$일 때의 결과물이 $12N-16$번 등장할 것을 예상할 수 있습니다.

 

따라서, $N$과 $M$에 따른 로쿰의 부피 $A(N,M)$은 다음과 같이 나타납니다.

$$A(N,M+1) = (12N-16)A(N,M) \rightarrow A(N,M) = (12N-16)^{M-1} \times A(N,1)$$

그런데 예시 그림을 관찰하면 $M=1$일 때 부피 1의 정육면체 역시 $12N-16$번 나타납니다. 즉

$$A(N,M) = (12N-16)^{M}$$

입니다.

 

이제 같은 방법으로 겉넓이를 파악하려하는 순간, 저는 몇 가지 시행착오를 거치게 되었습니다. 우선, 겉넓이는 $B(N,M)$으로 나타내겠습니다.

• $M=1$일 때의 로쿰의 겉넓이를 계산할 때 꼭짓점에서는 겉넓이 3, 나머지에서는 겉넓이 4를 갖는다고 생각했습니다. 물론 맞는 말이지만, $M=2$일 때 그대로 적용해버리면 파낸 부분을 올바르게 고려하지 못해 틀리게 됩니다.
• 파내지 않은 부분과 파낸 부분을 따로 생각하여 점화식을 따로 세우려 했습니다. 그런데 $M$이 커짐에 따라 첫 번째 파냈을 때와 두 번째 파냈을 때 등등을 생각하지 못하고, $M=1$일 때의 로쿰이 몇 번 나타나는 지만 생각하여 실패했었습니다.

제가 생각한 방식은, 일단 $M$번 반복한 결과물의 각각의 정육면체를 $N$배 확장시킵니다. 그때 각 정육면체를 파내면, $M=1$일 때의 로쿰이 몇 번 생기는지 파악할 수 있습니다. 바로 이 때 파낸 부분과 파내지 않은 부분의 넓이를 각각 계산하여 더하면 점화식이 올바르게 나옵니다. 먼저 파내지 않은 부분은 각 정사각형에 대해

$$N^{2} - (N-2)^{2} = 4N-4$$

만큼 남게 되는데, 확장시키기 전, 넓이가 1인 정사각형은 정확히 $B(N,M)$개 있었기 때문에 파내지 않은 부분의 넓이는

$$(4N-4) \times B(N,M)$$

만큼 $B(N,M+1)$에 기여하게 됩니다.

 

파낸 부분의 경우 각 정육면체에 대해

$$\left ( 4 \times \left ( N-2 \right ) \right ) \times 6 = 24N - 48$$

만큼 생기는데, 부피가 1인 정육면체는 확장 전 $A(N,M)$개 있었기 때문에

$$(24N-48) \times A(N,M)$$

만큼 기여합니다. (에디토리얼은 이 부분에서 사소한 실수를 했습니다.)

 

로쿰의 겉넓이는 파내진 부분, 혹은 파내지지 않은 부분밖에 없으므로 더 이상의 기여는 없습니다. 따라서,

$$B(N,M+1) = (4N-4) \times B(N,M) + (24N-48) \times A(N,M)$$

이며 $A,B$의 점화식은 행렬로 모델링하기 매우 쉬운 점화식입니다.

 

참고로, $M=0$일 때의 결과물을 부피 1의 정육면체 1개라고 가정한다면, $A(N,0)=1$, $B(N,0)=6$이며 이를 대입하면 $A,B$ 값을 복잡하게 생각하지 않아도 됩니다.

 

$$\begin{bmatrix} A(N,M) \\ B(N,M) \end{bmatrix} = \begin{bmatrix} 12N-16 & 0 \\ 24N-48 & 4N-4 \end{bmatrix} \begin{bmatrix} A(N,M-1) \\ B(N,M-1) \end{bmatrix}$$

$$\rightarrow \begin{bmatrix} A(N,M) \\ B(N,M) \end{bmatrix} = \begin{bmatrix} 12N-16 & 0 \\ 24N-48 & 4N-4 \end{bmatrix} ^{M} \begin{bmatrix} 1 \\ 6 \end{bmatrix}$$

이는 $O(\log M)$에 구할 수 있습니다. 제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, long long P);

int main() {
	
	long long N, M;
	scanf("%lld %lld", &N, &M);
	
	Matrix Base =
	{{
		{(12 * N - 16) % mod, 0},
		{(24 * N - 48) % mod, (4 * N - 4) % mod}
	}};
	
	Matrix Answer =
	{{
		{1, 0},
		{6, 0}
	}};
	
	Answer = matrix_multiply_modular(matrix_power_modular(Base, M), Answer);
	printf("%lld %lld", Answer.array[0][0], Answer.array[1][0]);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result = {{{}}};
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; 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, long long P) {
	Matrix result =
	{{
		{1, 0},
		{0, 1}
	}};
	while (P) {
		if (P % 2) {
			result = matrix_multiply_modular(result, A);
		}
		A = matrix_multiply_modular(A, A);
		P /= 2;
	}
	return result;
}

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

---

$S(N,M)$의 일반항을 구하여 푸는 풀이도 있습니다!