백준 17539: Keep Calm and Sell Balloons

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

17539번: Keep Calm and Sell Balloons

---

 

이 문제는 가로 길이 $N$ 이 주어질 때 지도 위의 $2N$ 개의 칸 중 임의의 한 칸에서부터

 

지도 위의 모든 칸을 순회하는 방법의 수를 구하는 문제입니다.

 

우선 $N$ 이 충분히 작은 경우부터 생각해보겠습니다.

 

---

 

$N=1$ 인 경우, 윗쪽 칸에서 시작하는 것과 아랫 칸에서 시작하는 두 가지 방법 뿐입니다.

 

$$\therefore Ans \left ( 1 \right ) = 2$$

 

---

 

$N=2$ 인 경우, 각각의 corner 에서 시작하는 경우의 수가 모두 동일함을 알 수 있습니다.

 

그리고, $N=2$ 에서 특별히 어느 칸에서 시작하든 나머지 세 칸에 모두 접근할 수 있습니다.

 

이런 성질을 감안하면 다음을 알 수 있습니다.

 

$$Ans \left ( 2 \right ) = 4\times 3\times 2\times 1 = 24$$

 

---

 

이제 $N=3$ 인 경우를 다룰 수 있을까요?

 

경우의 수가 96가지라는 것이 주어져있는데, 생각보다 쉽지 않습니다.

 

그래서 이쯤에서 점화식을 활용한 접근을 고려해보겠습니다.

 

$F \left ( N \right )$ : 가로 길이가 $N$ 인 $2\times N$ 직사각형의 왼쪽 위 꼭짓점에서 출발하여 $2N$ 개의 정점을 모두 순회하는 경우의 수

 

정의로부터, 다음을 알 수 있습니다.

 

$$Ans \left ( 1 \right ) = 2\times F \left ( 1 \right )$$

 

$$Ans \left ( 2 \right ) = 4\times F \left ( 2 \right )$$

 

그러면 $N$ 이 충분히 클 때 $F$ 에 관한 점화식을 알아보겠습니다.

 

 

---

 

일단 그림을 적당히 그려보았습니다.

 

 

위와 같이 $2N$ 개의 점에 번호를 매겼습니다. 우리는 1번 점에서 나머지 $2N-1$ 개의 점을 순회합니다.

 

점화 관계를 알아보는 시간이니까, $F \left ( N-1 \right )$ 과 $F \left ( N-2 \right )$ 등등을 최대한 활용해야 합니다.

 

1번 점에서 갈 수 있는 점들을 먼저 뽑는다면, 2번 3번 4번이 있습니다.

 

이 중에서 2번 점을 간 경우를 보면, $N-1$ 개의 column이 있는데 2번 column 의 두 점(3번, 4번) 중 하나로 도착하게 됩니다.

 

그리고 3번 or 4번 점에서부터 나머지 점을 순회하는 것은 $F \left ( N-1 \right )$ 입니다. 즉 다음을 얻습니다.

 

$$2\times F \left ( N-1 \right ) \in F\left ( N \right )$$

 

 

---

 

그러면 1번으로부터 3번 or 4번을 먼저 가면 어떨까요?

 

일단 1~4 번의 점을 모두 채우는 경우를 생각해보겠습니다. 즉 1~4번을 다 채운 뒤 5번 or 6번을 가는 것입니다.

 

이전과 마찬가지로, 5번 or 6번 부터는 $F\left ( N-2 \right )$ 임을 알 수 있습니다.

 

여기에 곱해지는 coefficient 을 구하는 것은 brute force입니다. 모두 나열해보면 다음과 같은 4가지 경우의 수입니다.

 

$$1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5$$

$$1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 6$$

$$1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5$$

$$1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 6$$

 

따라서 다음을 얻습니다.

 

$$4\times F \left ( N-2 \right ) \in F\left ( N \right )$$

 

 

---

 

위 두 가지 경우의 수를 제외한 다른 경우가 있을까요? 1번에서 3 or 4 로 간 경우를 더 생각해봅시다.

 

여기서 만약 1~4 번 칸에 머무른다면 중복입니다. 즉 5 or 6번 칸으로 뻗어가는 경우의 수를 생각해야 합니다.

 

여기서 다시 1~6 번 칸에 머무르면 중복일 것입니다. 즉 7 or 8 로 뻗어가야 합니다.

 

$\vdots$

 

이로부터 우리는 새로운 경로를 찾았습니다. 이는 곧 다음과 같습니다.

 

$N-1$ 개의 "column"에서 각각 한 개의 점을 골라서, $1 \rightarrow \cdots \rightarrow 2$ 로 순회가 끝나는 경로

 

따라서 다음을 얻습니다.

 

$$2^{N-1} \in F\left ( N \right )$$

 

$$F\left ( N \right ) = 2\times F\left ( N-1 \right ) + 4\times F\left ( N-2 \right ) + 2^{N-1}$$

 

이 점화식은 $N \geq 3$ 에서 성립함 역시 알 수 있습니다.

 

그러면 정답을 구한 걸까요? 사실 직사각형의 네 꼭짓점이 아닌 중간 점으로부터 출발하는 경우의 수도 생각해야 합니다.

 

 

---

 

이제 다음과 같은 경우를 생각해보겠습니다.

 

 

이는 $1 \leq K \leq N - 2$ 에 대한 그림입니다.

 

이 그림에서 가운데 column의 두 점 중 하나에서 출발하여, 나머지 점들을 순회하는 방법을 생각해봅시다.

 

이는 곧 시작 점에서부터 왼쪽을 먼저 가느냐, 오른쪽을 먼저 가느냐를 결정하는 문제로 바뀝니다.

 

---

 

먼저 K columns 방향으로 나아갔다고 하면, 이는 곧 $F \left ( K \right )$ 아닐까요?

 

실제로는 $F\left ( K \right )$ 로 나타내어지는 경로는 너무 많습니다. 순회하여 시작 column으로 돌아오는 경로만 선택해야 합니다.

 

그러므로 다른 방법으로 경로를 선택해야 하는데, 이는 $2^{K}$ 가지 존재함을 이전에 확인했습니다.

 

다시 시작 column으로 돌아왔다면, N-K-1 column 의 점들을 모두 순회하면 끝입니다.

 

따라서 이 경우는 다음과 같습니다.

 

$$2^{K} \times 2 \times F \left ( N-K-1 \right )$$

 

 

---

 

이제 오른쪽으로 먼저 갔다면 같은 방법으로 다음을 얻습니다.

 

$$2^{N-K-1} \times 2 \times F \left ( K \right )$$

 

이로써 답을 구할 준비가 모두 끝났습니다!

 

---

 

이제 답을 구하겠습니다.

 

세로 길이 2, 가로 길이 $N$ 인 총 $2N$ 칸의 직사각형에서, 1번, 2번, $2N-1$ 번, $2N$ 번 칸에서 출발할 수 있습니다.

 

그러므로 다음을 얻습니다.

 

$$4\times F\left ( N \right ) \in ANS$$

 

이제 가운데에서 시작하는 경우를 생각하겠습니다. 임의의 column을 잡고 그 column의 점이 2개임을 고려하면 다음을 얻습니다.

 

$$ANS \ni 2\times \sum_{k=1}^{N-2} \left ( 2^{K} \times 2 \times F \left ( N-K-1 \right ) + 2^{N-K-1} \times 2 \times F \left ( K \right ) \right )$$

 

이는 실제로 모든 경우의 수를 탐색한 것입니다. 따라서 우리가 찾는 답은 다음과 같습니다.

 

$$ANS = 4\times F\left ( N \right ) + 2\times \sum_{k=1}^{N-2} \left ( 2^{K} \times 2 \times F \left ( N-K-1 \right ) + 2^{N-K-1} \times 2 \times F \left ( K \right ) \right )$$

 

식 정리를 해보겠습니다.

 

$$ANS = 4\times F\left ( N \right ) + 4\times \sum_{k=1}^{N-2} \left ( 2^{K} \times F \left ( N-K-1 \right ) + 2^{N-K-1} \times F \left ( K \right ) \right )$$

 

$$ANS = 4\times F\left ( N \right ) + 8\times \sum_{k=1}^{N-2} 2^{N-K-1} \times F \left ( K \right )$$

 

여기까지만 해도 답은 충분히 구할 수 있습니다. $F \left ( N \right )$ 에 대한 점화관계가 행렬로 쉽게 표현 가능하기 때문입니다.

 

그러나 좀 더 식을 간단히 줄일 수 있는 풀이가 존재합니다. 다소 발상적이긴 하지만, 요점은 $\sum$ 의 $2^{N-K-1}$ 을 소거하는 것입니다.

 

---

 

이제 다음과 같은 함수 $G$ 를 도입합니다.

 

$$F\left ( N \right )=2^{N-1}\times G\left ( N \right )$$

 

이를 점화식에 대입하면 다음을 얻습니다.

 

$$2^{N-1}\times G\left ( N \right ) = 2\times 2^{N-2} \times G\left ( N-1 \right ) + 4\times 2^{N-3} \times G\left ( N-2 \right ) + 2^{N-1}$$

 

$$G\left ( N \right ) = G\left ( N-1 \right ) + G\left ( N-2 \right ) + 1$$

 

한편 우리가 구했던 ANS에도 $G$ 을 대입해보겠습니다.

 

$$ANS = 4\times 2^{N-1}\times G\left ( N \right ) + 8\times \sum_{k=1}^{N-2} 2^{N-K-1} \times 2^{K-1}\times G \left ( K \right )$$

 

$$ANS = 2^{N+1}\times G\left ( N \right ) + 8\times \sum_{k=1}^{N-2} 2^{N-2} \times G \left ( K \right )$$

 

$$ANS = 2^{N+1}\times G\left ( N \right ) + 2^{N+1}\times \sum_{k=1}^{N-2} \times G \left ( K \right )$$

 

---

 

이상의 식에서 $G$ 의 합을 우리가 아직 구하지 못했습니다. 한 번 $G$ 를 나열해볼까요?

 

$$G\left ( 3 \right ) = G\left ( 2 \right ) + G\left ( 1 \right ) + 1$$

$$G\left ( 4 \right ) = G\left ( 3 \right ) + G\left ( 2 \right ) + 1$$

$$G\left ( 5 \right ) = G\left ( 4 \right ) + G\left ( 3 \right ) + 1$$

$$\vdots$$

$$G\left ( N-2 \right ) = G\left ( N-3 \right ) + G\left ( N-4 \right ) + 1$$

$$G\left ( N-1 \right ) = G\left ( N-2 \right ) + G\left ( N-3 \right ) + 1$$

$$G\left ( N \right ) = G\left ( N-1 \right ) + G\left ( N-2 \right ) + 1$$

 

위 나열을 모두 더하게 되면 다음을 얻습니다.

 

$$\sum_{i=3}^{N} G\left ( i \right ) = G\left( N-1 \right ) + 2 \times \sum_{i=2}^{N-2} G\left ( i \right ) + \left ( N-2 \right )$$

 

이제 위 식을 다시 변형해보겠습니다.

 

$$\sum_{i=1}^{N} G\left ( i \right ) = G\left( N-1 \right ) + 2 \times \sum_{i=2}^{N-2} G\left ( i \right ) + G\left ( 2 \right ) + G\left ( 1 \right ) + \left ( N-2 \right )$$

 

$$G\left ( N \right ) = \sum_{i=1}^{N-2} G\left ( i \right ) + G\left ( 2 \right ) + \left ( N-2 \right )$$

 

$$\sum_{i=1}^{N-2} G\left ( i \right ) = G\left ( N \right ) - \left ( N+1 \right )$$

 

---

 

그러므로 $N$ 이 주어졌을 때 정답은 다음과 같습니다.

 

$$ANS = 2^{N+1}\times G\left ( N \right ) + 2^{N+1}\times \left ( G\left ( N \right ) - \left ( N+1 \right ) \right )$$

 

$$ANS = 2^{N+2}\times G\left ( N \right ) - \left ( N+1 \right ) \times 2^{N+1}$$

 

---

 

마지막으로 큰 $N$ 값에 대해 빠른 시간 안에 구할 수 있도록 $G$ 에 관한 행렬 형태의 점화식을 찾겠습니다.

 

기존의 점화식은 다음과 같았습니다.

 

$$G\left ( N \right ) = G\left ( N-1 \right ) + G\left ( N-2 \right ) + 1$$

 

이로부터 다음을 얻을 수 있습니다.

 

$$\begin{bmatrix} G\left ( N \right ) \\ G\left ( N-1 \right ) \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} G\left ( N-1 \right ) \\ G\left ( N-2 \right ) \\ 1 \end{bmatrix}$$

 

이제 $G\left ( N \right )$ 은 다음 식을 통해 $O\left ( \log N \right )$ 에 얻을 수 있습니다.

 

$$\begin{bmatrix} G\left ( N \right ) \\ G\left ( N-1 \right ) \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} ^{N-2} \begin{bmatrix} G\left ( 2 \right ) \\ G\left ( 1 \right ) \\ 1 \end{bmatrix}$$

 

음수 모듈러 연산에 주의하여 이상의 내용을 잘 구현하면 됩니다. 제 코드는 다음과 같습니다.

 

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

#include <stdio.h>
#define mod 1000000007

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

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

long long power_modular (long long A, int power);

int small_ans[] = {0, 2, 24, 96, 416};

int main() {
	
	int N;
	scanf("%d", &N);
	
	if (N <= 4)
	{
		printf("%d", small_ans[N]);
		return 0;
	}
	
	Matrix Base =
	{{
		{1, 1, 1},
		{1, 0, 0},
		{0, 0, 1}
	}};
	Base = matrix_power_modular(Base, N - 2);

	long long ANS = (3 * Base.array[0][0] + Base.array[0][1] + Base.array[0][2]) % mod;
	
	long long temp = power_modular(2, N+1);
	
	ANS = ANS * (temp * 2 % mod) % mod;
	
	temp = temp * (N + 1) % mod; // temp := (N+1) * 2^(N+1)

	ANS = (ANS - temp) % mod;
	while (ANS < 0)
	{
		ANS += mod;
	}
	
	printf("%lld", ANS);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B)
{
	Matrix result = {{{0}}};
	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;
}

long long power_modular (long long A, int power)
{
	long long result = 1;
	while(power)
	{
		if (power % 2)
		{
			result = result * A % mod;
		}
		A = A * A % mod;
		power /= 2;
	}
	return result;
}

 

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

---

 

최종적으로 행렬 점화식의 응용으로 풀리는 문제이기 때문에 Berlekamp-Massey, Kitamasa 의 적용이 가능합니다.

 

이를 위해서는 초기값들을 몇 가지 구해봐야 하는데, 공개해드리고자 합니다. $N \leq 10$ 일 때의 정답입니다.

 

$$2,24,96,416,1536,5504,18944,64000,212992,702464$$