백준 15570번 : 블록 2

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

15570번: 블록 2

---

이 문제는 일단 타일 채우기 문제들과 비슷하게 접근할 수 있습니다.

 

일단 저의 경우, 문제에서 $N \times M$ 크기의 블록이 세로로 $N$ , 가로로 $M$ 의 크기라고 생각했습니다.

 

이때 $N \times M$ 크기를 작은 블록들로 만드는 방법의 수를 다음과 같이 쓰겠습니다.

 

$$ A \left ( N \; , \; M \right ) $$

 

이 문제에서 $M > N$ 일 가능성이 압도적으로 크기 때문에, 해당 경우부터 우선 점화식을 유도하겠습니다.

 

---

 

우선 가로의 길이가 $M$ 인데, 이를 다음과 같이 쪼갠다고 생각할 수 있습니다.

 

$$M =1 + \left ( M - 1 \right )$$

$$ = 2 + \left ( M - 2 \right ) $$

$$ = 3 + \left ( M - 3 \right ) $$

$$ = 4 + \left ( M - 4 \right ) $$

$$ \vdots $$

$$ = N + \left ( M - N \right ) $$

 

즉 다음을 알 수 있습니다.

 

$$ A \left ( N \; , \; M \right ) = \sum_{k=1}^{N} A \left ( N \; , \; k \right ) A \left ( N \; , \; M-k \right ) $$

 

그래서 $ A \left ( N \; , \; 1 \right ) $ 의 값부터 관찰해봐야 하겠습니다.

---

 

$N$ 이 충분히 크다고 생각하면, 일단 확실하게 다음을 알 수 있습니다.

 

$$ A \left ( N \; , \; 1 \right ) = 1 $$

 

그리고 $M=2$ 일 때를 관찰하면

 

2를 1 두 개로 채우는 것과 2 짜리 하나로 채우는 걸 상상할 수 있습니다.

 

그래서 다음을 알 수 있습니다.

 

$$ A \left ( N \; , \; 2 \right ) = 2 $$

 

이제 $M=3$ 일 때를 생각하겠습니다.

 

$$ 3=1+1+1 $$

$$ =1+2 $$

$$ =2+1 $$

 

따라서 다음을 얻습니다.

 

$$ A \left ( N \; , \; 3 \right ) = 4 $$

 

규칙이 보이시나요? 이제 수식적으로 한 번 풀어보겠습니다.

 

$M > N$ 일 때와 같은 논리로, $M < N$ 일 때도 다음 식을 얻을 수 있습니다.

 

$$ A \left ( N \; , \; M \right ) = 1 + \sum_{k=1}^{M-1} A \left ( N \; , \; M-k \right ) $$

 

이 점화식과 수학적 귀납법을 통해 다음을 증명할 수 있습니다. $\left ( M < N \right )$

 

$$A\left ( N \; , \; M \right ) = 2^{M-1} $$

 

---

 

이제 $M=N$ , 즉 $A \left ( N \; , \; N \right )$ 을 구해보겠습니다.

 

일단 기존의 접근 방식을 토대로 다음을 얻습니다.

 

$$ A \left ( N \; , \; N \right ) \geq 1 + \sum_{k=1}^{N-1} A \left ( N \; , \; N-k \right ) $$

 

그런데 우리가 채워야 하는 블록의 크기가 $N \times N$ 이라는 것은, 블록을 눕혀서 채울 수도 있다는 뜻입니다.

 

이를 통해 블록을 눕혀서 채우는 경우의 수를 산출해보면 다음을 얻을 수 있습니다.

 

$$ A \left ( N \; , \; N \right ) = 1 + 2 \times \sum_{k=1}^{N-1} A \left ( N \; , \; N-k \right ) $$

 

따라서 $A \left ( N \; , \; N \right )$ 은 다음과 같습니다.

 

$$ A \left ( N \; , \; N \right ) = 2^{N} - 1$$

 

---

 

이쯤에서 다시 처음의 점화식을 관찰하겠습니다.

 

$$ A \left ( N \; , \; M \right ) = \sum_{k=1}^{N} A \left ( N \; , \; k \right ) A \left ( N \; , \; M-k \right ) $$

 

이 방식대로도 물론 계산이 가능한데, naive하게 보면 $O \left ( NM \right )$ 일 것입니다.

 

최적화를 위해 점화식을 행렬의 형태로 나타내겠습니다.

 

$$ \begin{bmatrix} A \left ( N \; , \; M \right ) \\ A \left ( N \; , \; M-1 \right ) \\ A \left ( N \; , \; M-2 \right ) \\ \vdots \\ A \left ( N \; , \; M-N+1 \right ) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 2^{N-1} \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \begin{bmatrix} A \left ( N \; , \; M-1 \right ) \\ A \left ( N \; , \; M-2 \right ) \\ A \left ( N \; , \; M-3 \right ) \\ \vdots \\ A \left ( N \; , \; M-N \right ) \end{bmatrix} $$

 

이를 통해 다음을 얻습니다.

 

$$ \begin{bmatrix} A \left ( N \; , \; M \right ) \\ A \left ( N \; , \; M-1 \right ) \\ A \left ( N \; , \; M-2 \right ) \\ \vdots \\ A \left ( N \; , \; M-N+1 \right ) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 2^{N-1} \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 0 \end{bmatrix} ^{M-N} \begin{bmatrix} A \left ( N \; , \; M-1 \right ) \\ A \left ( N \; , \; M-2 \right ) \\ A \left ( N \; , \; M-3 \right ) \\ \vdots \\ A \left ( N \; , \; M-N \right ) \end{bmatrix} $$

 

이제 시간 복잡도는 대략 $O \left ( N^{3}\log M \right )$ 으로 줄었습니다.

 

한편, $N=1$ 일 때 정답은 반드시 1임에 주의하여 코드를 구현하면 됩니다.

 

정답 코드는 다음과 같습니다.

---

#include <stdio.h>
#define mod 1999

typedef struct {
	int array[100][100];
} Matrix;

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

int main() {
	
	int N;
	long long M;
	scanf("%d %lld", &N, &M);
	
	if (N == 1) {
		printf("1");
		return 0;
	}
	
	if (N == M) {
		int answer = 1;
		for (int i = 0; i < N; i++) {
			answer = 2 * answer % mod;
		}
		printf("%d", answer - 1);
		return 0;
	}
	
	if (N > M) {
		int answer = 1;
		for (int i = 0; i < M - 1; i++) {
			answer = 2 * answer % mod;
		}
		printf("%d", answer);
		return 0;
	}
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < N - 1; i++) {
		Base.array[0][i] = 1;
        Base.array[i+1][i] = 1;
	}
	int temp = 1;
	for (int i = 1; i < N; i++) {
		temp = 2 * temp % mod;
	}
	Base.array[0][N-1] = temp;
	
	Matrix Answer = { {{0}} };
	Answer.array[N-1][0] = 1;
	for (int i = N - 2; i > 0; i--) {
		Answer.array[i][0] = 2 * Answer.array[i+1][0] % mod;
	}
	Answer.array[0][0] = (2 * temp - 1) % mod;
	
	Base = matrix_power_modular(Base, M - N, N);
	Answer = matrix_multiply_modular(Base, Answer, N);
	
	printf("%d", Answer.array[0][0]);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; 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, int size) {
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++) {
		result.array[i][i] = 1;
	}
	while(P > 0) {
		if (P & 1) {
			result = matrix_multiply_modular(A, result, size);
		}
		A = matrix_multiply_modular(A, A, size);
		P >>= 1;
	}
	return result;
}

(C11, 1344KB, 36ms, 제출번호 31758531번)

---