백준 13976번: 타일 채우기 2

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

13976번: 타일 채우기 2

---

타일 채우기라고 부르는 유형은 풀이법이 어느정도는 정해져 있습니다.

 

보통 점화식을 구해야하는데, 그 과정에서, 다음 과정을 거칩니다.

 

1. 작은 $N$ 값에 대해 답을 구해봅니다
2. 적당히 큰 값의 $X$ 에 대해서, 가로로 $X$ 만큼의 크기(이 문제에서는 $3\;by\;X$ )를 얻었다고 칩니다
3. 그 다음 $X+1$ , $X+2$ , 로 확장해가면서 점화식을 추론합니다

 

이 글에서도 위와 같은 과정을 거칠 것입니다.

 

우선 $N=2$ 일 때, 답은 3입니다.

 

다음과 같은 경우의 수가 있습니다.

 

1. $N=2$ 일 때의 3가지 경우의 수

 

$N=4$ 일 때, 답은 11입니다.

 

다음과 같은 경우의 수가 있습니다.

 

2.1. $N=4$ 일 때의 경우의 수 9가지. 기존에 만들었던 블럭을 재활용

 

답을 11이라 했는데 9가지만 제시했죠? 일단 이 9가지는 $N=2$ 일 때의 경우의 수를 활용해서 만든 것입니다.

 

그리고 남은 2가지는 완전히 새롭게 생긴 것입니다.

 

2.2. $N=4$ 일 때의 경우의 수 2가지.새로 생긴 도형(이하 길이가 4인 odd)

 

이렇게 해서 $N=4$ 일 때의 11가지 경우의 수가 완성 됐습니다.

 

$N=6,\;8,\;10,\;\cdots$ 의 경우도 직접 구할 수는 있습니다.

 

하지만, 수열을 이렇게 정의해보겠습니다.

 

$\left \{ a_{n}\right \}$ : $3\times n$ 크기의 직사각형을 만드는 방법의 수

 

그러면, 적당히 큰 $x$ 에 대해, $a_{x},\;a_{x-2}\;\cdots\;a_{2}$ 을 통해 $a_{x+2}$ 를 만들어 보겠습니다.

 

또한 그림 2.2. 와 같은 형태가 모든 $N\geq2$ 에 대해 존재한다고 가정하겠습니다.

 

그 형태를 odd 라고 부르겠습니다.

 

이제 $a_{x+2}$ 를 만드는 방법은,

 

$a_{2}$ 의 상태에서, 가로 길이가 $x$ 인 odd 2가지

$a_{4}$ 의 상태에서, 가로 길이가 $x-2$ 인 odd 2가지

$\vdots$

$a_{x-2}$ 의 상태에서, 가로 길이가 $4$ 인 odd 2가지

$a_{x}$ 의 상태에서 남은 $3\times 2$ 공간을 채울 방법 $a_{2}=3$ 가지

$x+2$ 의 길이를 갖는 odd가 2가지

 

따라서, 다음 식이 유도됩니다.

 

$a_{x+2}=3\times a_{x}+2\times \left ( a_{x-2}+a_{x-4}+\cdots+a_{2} \right )+2$

 

여기까지 했다면 마지막 스텝이 남았습니다.

 

점화식의 크기가 $x$ 에 비례하고, $N$ 의 상한이 아주 큰 값이어서 식을 변형해야 합니다.

 

위 식에 따라 다음을 얻습니다.

 

$a_{x}=3\times a_{x-2}+2\times \left ( a_{x-4}+a_{x-6}+\cdots+a_{2} \right )+2$

 

이제 식끼리 빼면, 공통 부분이 삭제되면서 다음을 얻습니다.

 

$a_{x+2}=4\times a_{x}-a_{x-2}$

 

이를 행렬로 표현하면 다음과 같습니다.

 

$\begin{bmatrix} a_{x+2} \\ a_{x} \end{bmatrix}=\begin{bmatrix} 4 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{x} \\ a_{x-2} \end{bmatrix}$

 

$x$ 가 충분히 큰 값이었음에 주의하며, 최종적으로 다음 식을 얻습니다.

 

$\begin{bmatrix} a_{N} \\ a_{N-2} \end{bmatrix}=\begin{bmatrix} 4 & -1 \\ 1 & 0 \end{bmatrix}^{\frac{N}{2}} \begin{bmatrix} a_{2} \\ a_{0} \end{bmatrix}$

 

그런데 $a_{0}$ 에는 어떤 값이 들어가야 할까요?

 

점화식에 $x=2$ 를 대입하면, $a_{4}=4\times a_{2}-a_{0}$ 이므로, $a_{0}=1$ 이라 말할 수 있습니다.

 

애초에 문제에서 주어지는 $N>0$ 이므로 $a_{0}$ 값은 아귀가 맞기만 하면 충분합니다.

 

그래서, 우리가 계산해야 할 것은 다음과 같습니다.

 

$\begin{bmatrix} a_{N} \\ a_{N-2} \end{bmatrix}=\begin{bmatrix} 4 & -1 \\ 1 & 0 \end{bmatrix}^{\frac{N}{2}} \begin{bmatrix} 3 \\ 1 \end{bmatrix}$

 

 

한편, 우리가 구한 것은 $N$ 이 짝수인 경우이지만, $N$ 이 홀수인 경우의 답은 쉽게 알 수 있습니다.

 

사용할 수 있는 블록의 넓이는 모두 짝수인데, $N$ 이 홀수이면 $3\times N$ 도 홀수이므로 전부 채울 수 없습니다.

 

따라서 경우의 수는 0입니다.

 

 

예외처리와 음수 모듈러에 주의하며 구현한 최종 코드는 다음과 같습니다.

#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 Base, long long power);

int main() {
	
	long long N;
	scanf("%lld", &N);
	
	if (N % 2) {
		printf("0");
	}
	else {
		Matrix Base = { {{0,1},{-1,4}} };
		Matrix Answer = { {{1,0},{3,0}} };
		
		Base = matrix_power_modular (Base, N/2);
		Answer = matrix_multiply_modular (Base, Answer);
		
		printf("%lld", Answer.array[0][0]);
	}
	return 0;
}

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

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

(1116KB, 0ms, 제출번호 31122126)

---

이 글을 올리는 시점에선, 문제에 대해 아직 잘 모르는 게 좀 있습니다.

 

왜 odd는 항상 두 개만 존재할 수 있을까요?

 

$a_{0}=1$ 인 것은 $\binom{0}{0}=1$ 인 것처럼 뭔가 의미부여가 가능할 수는 있지만

 

odd에 관한 것은 잘 모르겠습니다.