백준 14553번: The Way

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

14553번: The Way

---

 

처음에 dp 식을 이상한 방향으로 접근해서 오랫동안 힘들었던 문제입니다.

우선 제가 AC 받은 접근은, $3 \times N$ 격자를 가장 왼쪽의 1열에서 2열로 넘어가는 모양새를 기준으로 subproblem을 나눕니다.

 

이게 무슨 뜻인지 경우의 수를 나누어 설명하겠습니다.

1. 시작하는 칸에서 바로 오른쪽으로 이동 : 2열의 윗 칸에서 N열의 아랫 칸으로 가는 경우의 수
2. 시작하는 칸에서 2열의 가운데 칸으로 이동 : 2열의 가운데 칸에서 N열의 아랫 칸으로 가는 경우의 수
3. 시작하는 칸에서 2열의 아래 칸으로 이동 : 2열의 아랫 칸에서 N열의 아랫 칸으로 가는 경우의 수

(단, 이 경우의 수는 1열의 칸들을 지나지 않는 경우의 수입니다.)

이렇게 하면 1번을 $A_{N-1}$, 2번을 $B_{N-1}$, 3번을 $C_{N-1}$이라 할 때 다음이 성립하는 것처럼 보입니다...!

$$ A_{N} = A_{N-1} + B_{N-1} + C_{N-1} $$

하지만 $N=2$일 때부터 위 점화식이 틀렸다는 걸 알 수 있습니다. 저희가 놓친게 있다는 뜻입니다.

 

이를 알기 위해 $N=2$일 때의 모든 경로를 나열하다보면, 특이하게 ㄹ자 모양의 경로가 있다는 걸 알 수 있습니다.

바로 이러한 모양새의 경로가 저희가 놓친 예외입니다. 이제 충분히 큰 $N$에서 예외를 논해보겠습니다.

---

편의를 위해 $k$열의 위 칸을 $a_{k}$, 가운데 칸을 $b_{k}$, 아래 칸을 $c_{k}$라고 하겠습니다.

첫번째 예외는 다음과 같은 경로입니다.

$$ a_{1} \rightarrow a_{2} \rightarrow b_{2} \rightarrow b_{1} \rightarrow c_{1} \rightarrow c_{2} \rightarrow c_{3} \rightarrow \cdots \rightarrow c_{N} $$

이때 정의에 의해 $c_{3}$부터 $c_{N}$까지 가는 경로의 수는 $C_{N-2}$입니다.

 

두번째 예외는 다음과 같은 경로입니다.

$$ a_{1} \rightarrow a_{2} \rightarrow a_{3} \rightarrow b_{3} \rightarrow b_{2} \rightarrow b_{1} \rightarrow c_{1} \rightarrow c_{2} \rightarrow c_{3} \rightarrow c_{4} \rightarrow \cdots \rightarrow c_{N} $$

이때 정의에 의해 $c_{3}$부터 $c_{N}$까지 가는 경로의 수는 $C_{N-3}$입니다.

 

이런 흐름으로 $k$번째 예외를 다음과 같이 정합니다.

$$ a_{1} \rightarrow \cdots \rightarrow a_{k+1} \rightarrow b_{k+1} \rightarrow \cdots \rightarrow b_{1} \rightarrow c_{1} \rightarrow \cdots \rightarrow c_{k+2} \rightarrow \cdots \rightarrow c_{N} $$

경로의 수는 $C_{N-k-1}$ 입니다.

 

이러한 예외는 결국 $N-1$개 있을 것입니다. 하지만, 경로의 수에서 $C_{1}$, $C_{0}$ 이라는 표현을 쓰게 되는데 정의와 충돌하는지 검토해야합니다.

$N=4$일 때, 각각의 예외가 다음과 같습니다.

$$ a_{1} \rightarrow a_{2} \rightarrow b_{2} \rightarrow b_{1} \rightarrow c_{1} \rightarrow c_{2} \rightarrow c_{3} \rightarrow \cdots \rightarrow c_{4} $$

$$ a_{1} \rightarrow a_{2} \rightarrow a_{3} \rightarrow b_{3} \rightarrow b_{2} \rightarrow b_{1} \rightarrow c_{1} \rightarrow c_{2} \rightarrow c_{3} \rightarrow c_{4} $$

$$ a_{1} \rightarrow \cdots \rightarrow a_{4} \rightarrow b_{4} \rightarrow \cdots \rightarrow b_{1} \rightarrow c_{1} \rightarrow \cdots \rightarrow c_{4} $$

그런데 두번째 경로의 수를 어떻게 표기할 수 있을까요?

 

$A_{i}$, $B_{i}$, $C_{i}$를 보다 엄밀하게 다시 정의합니다.

1. $A_{i}$ : $3 \times i$ 격자에서, $a_{1}$에서 출발하여 $c_{i}$로 도착하는, 한번 지나간 칸을 다시 지나지 않는 경로의 수
2. $B_{i}$ : $3 \times i$ 격자에서, $b_{1}$에서 출발하여 $c_{i}$로 도착하는, 한번 지나간 칸을 다시 지나지 않는 경로의 수
3. $C_{i}$ : $3 \times i$ 격자에서, $c_{1}$에서 출발하여 $c_{i}$로 도착하는, 한번 지나간 칸을 다시 지나지 않는 경로의 수

 

이렇게 정의했을 때 두번째 경로의 수, 즉 $C_{1}$은 정의에 부합한다고 볼 수는 있습니다. 그러나 이렇게 해도 $C_{0}$은 와닿지 않습니다.

따라서 $A_{i}$, $B_{i}$, $C_{i}$의 정의역을 자연수로 유지하고, 특별히 세번째와 같이 $a_{1}$부터 $c_{N}$까지 모든 칸을 ㄹ 모양으로 지나가는 경로가 1가지 있음에 유의하겠습니다.

---

결과적으로 $A$에 관한 점화식을 다음과 같이 얻을 수 있습니다.

$$ A_{N} = A_{N-1} + B_{N-1} + C_{N-1} + C_{N-2} + \cdots + C_{1} + 1 $$

마찬가지로 $B$, $C$에 대해서도 점화식을 얻을 수 있습니다.

 

$$ B_{N} = A_{N-1} + B_{N-1} + C_{N-1} $$

$$ C_{N} = A_{N-1} + A_{N-2} + \cdots + A_{1} + B_{N-1} + C_{N-1} $$

이때, $c_{1}$에서 출발하여 $c_{N}$까지 역 ㄹ 방향으로 모든 칸을 지나가는 경로는 없음에 주의해주세요.

---

여기까지 점화식을 유도해냈다면, $O \left ( N \right )$ dp로 풀어도 충분히 답을 얻을 수 있습니다. 그러나, 저는 $N$이 충분히 큰 경우에도 답을 구할 수 있게 점화식을 바꿔보고 싶었습니다.

이에 따라 다음 두 수열을 도입합니다.

$$ D_{N} = \sum_{i=1}^{N} A_{i} $$

$$ E_{N} = \sum_{i=1}^{N} C_{i} $$

$D$, $E$의 정의에 따라 $D$, $E$에 대한 점화식이 각각 다음과 같습니다.

$$ D_{N+1} = \sum_{i=1}^{N+1} A_{i} = A_{N+1} + D_{N} $$

$$ E_{N+1} = \sum_{i=1}^{N} C_{i} = C_{N+1} + E_{N} $$

한편 $D$, $E$에 의해 $A$, $C$의 점화식이 다음과 같이 변합니다.

$$ A_{N+1} = A_{N} + B_{N} + C_{N} + C_{N-1} + \cdots + C_{1} + 1 = A_{N} + B_{N} + E_{N} + 1 $$

$$ C_{N+1} = A_{N} + B_{N} + C_{N} + A_{N-1} + \cdots + A_{1} + 1 = B_{N} + C_{N} + D_{N} $$

이를 바탕으로 $D$, $E$의 점화식을 다시 쓰면 다음과 같습니다.

$$ D_{N+1} = A_{N} + B_{N} + D_{N} + E_{N} + 1 $$

$$ E_{N+1} = B_{N} + C_{N} + D_{N} + E_{N} $$

마지막으로, 다음과 같이 행렬을 응용한 표현(행렬열?)을 도입합니다.

$$ \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ 1 \end{bmatrix}_{N} = \begin{bmatrix} A_{N} \\ B_{N} \\ C_{N} \\ D_{N} \\ E_{N} \\ 1 \end{bmatrix} $$

이제 행렬 점화식을 다음과 같이 얻을 수 있습니다!

$$ \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ 1 \end{bmatrix}_{N+1} = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ 1 \end{bmatrix}_{N} $$

---

최종적으로 저희가 구현할 것은 다음 식입니다.

$$ \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ 1 \end{bmatrix}_{N} = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}^{N-1} \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ 1 \end{bmatrix}_{1} $$

한편, 정의에 따라 다음이 성립함을 알 수 있습니다.

$$ A_{1} = B_{1} = C_{1} = D_{1} = E_{1} = 1 $$

그러므로, 저희는 $A_{N}$만 관심있기 때문에, 위 식에서 Base matrix의 exponential만 구한 뒤 top row entries를 summation해도 정답을 얻을 수 있습니다.

 

다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000009
 
typedef struct {
	long long array[6][6];
} Matrix;
 
Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, int P);
 
int main(void) {
 
	int N;
	scanf("%d", &N);
 
	Matrix Base =
	{{
		{1, 1, 0, 0, 1, 1},
		{1, 1, 1, 0, 0, 0},
		{0, 1, 1, 1, 0, 0},
		{1, 1, 0, 1, 1, 1},
		{0, 1, 1, 1, 1, 0},
		{0, 0, 0, 0, 0, 1}
	}};
	Base = matrix_power_modular(Base, N-1);
 
	long long answer = 0;
	for (int i = 0; i < 6; i++) {
		answer = (answer + Base.array[0][i]) % mod;
	}
 
	printf("%lld", answer);
	return 0;
}
 
Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result = {{{}}};
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			for (int k = 0; k < 6; 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 P) {
	Matrix result = {{{}}};
	for (int i = 0; i < 6; i++) {
		result.array[i][i] = 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, 제출번호 54196757)

---

이 방법론은 다음 글에서 배웠습니다 : https://yulran.tistory.com/54

 

한편, 이 문제는 2017 KAIST에서 나온 문제인데, 에디토리얼에서는 원본 문제가 $N \leq 10^{6}$이었다고 합니다.

어차피 $N \leq 1000$에서부터 백트래킹은 답이 될 수 없으니 원본대로 $N$이 주어져도 $O \left ( N \right )$이 정해였을 것 같긴 합니다.

저의 경우는, 복잡도 $O \left ( \log N \right )$이기 때문에, $N \leq 10^{18}$까지 가능할 것 같습니다!