백준 19587번: 객실 배치

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

19587번: 객실 배치

---

이전 포스팅과( 12878번: Blocks ) 방법론이 비슷한 문제입니다.

 

다만, 이전 포스팅에서는 모든 state의 경우의 수를 문제에서 답으로써 요구하지는 않았습니다.

 

그 점에서, 이번 문제는 정답에 해당하는 경우를 여러 state로 나눠 본다는 차이가 있습니다.

 

$N=1$ 일 때의 예제 해설에 따라서, $N$ 층까지 사람을 조건에 맞게 배치한 경우를 생각해 봅시다.

 

이때, $N$ 층에 대하여 다음과 같은 state 들이 존재한다고 할 수 있습니다.

 

$\left ( a \right )$ $N\times 100 + 1$ 호에 사람이 묵는 경우

$\left ( b \right )$ $N\times 100 + 2$ 호에 사람이 묵는 경우

$\left ( c \right)$ $N$ 층에 사람을 배치하지 않는 경우

 

각각을 함수로 정의해 봅시다.

 

$N\times 100 + 1$ 호에 사람을 배치하는 경우의 수 $A\left ( N \right )$

$N\times 100 + 2$ 호에 사람을 배치하는 경우의 수 $B\left ( N \right )$

$N$ 층 양 객실에 사람을 배치하지 않는 경우의 수 $C\left ( N \right)$

 

이제 $N$ 층까지 사람을 적절하게 배치한 다음, $N+1$ 층에 사람을 배치하는 방법에 대해 생각해봅시다.

 

$\left ( 1 \right )$ $N$ 층에 대해 $\left ( c \right )$ 인 경우, 두 객실 중 어느 곳에라도 배치할 수 있습니다.

즉, 두 객실 모두에 사람을 배치하지 않을 수도 있습니다.

 

$\left ( 2 \right )$ $N$ 층에 대해 $\left ( a \right )$ 인 경우, $N\times 100 + 2$ 호에 사람을 배치하거나,

두 객실 모두에 사람을 배치하지 않을 수 있습니다.

 

$\left ( 3 \right )$ $N$ 층에 대해 $\left ( b \right )$ 인 경우, $N\times 100 + 1$ 호에 사람을 배치하거나,

두 객실 모두에 사람을 배치하지 않을 수 있습니다.

 

결과적으로, $A\left ( N \right )\sim C\left ( N \right )$ 에 대한 점화식이 다음과 같습니다.

 

$A\left ( N+1 \right ) = B\left ( N \right ) + C\left ( N \right )$

$B\left ( N+1 \right ) = A\left ( N \right ) + C\left ( N \right )$

$C\left ( N+1 \right) = A \left ( N \right ) + B\left ( N \right ) + C\left ( N \right)$

 

이를 행렬로 옮기면 다음과 같습니다.

 

$\begin{bmatrix} A\left ( N+1 \right ) \\ B\left ( N+1 \right ) \\ C\left ( N+1 \right ) \end{bmatrix}$ $=$ $\begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}$ $\begin{bmatrix} A\left ( N \right ) \\ B\left ( N \right ) \\ C\left ( N \right ) \end{bmatrix}$

 

최종적으로 다음 식을 얻을 수 있습니다.

 

$\begin{bmatrix} A\left ( N \right ) \\ B\left ( N \right ) \\ C\left ( N \right ) \end{bmatrix}$ $=$ $\begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^{N-1}$ $\begin{bmatrix} A\left ( 1 \right ) \\ B\left ( 1 \right ) \\ C\left ( 1 \right ) \end{bmatrix}$

 

이때 정의에 따라 $A\left ( 1 \right )=B\left ( 1 \right )=C\left ( 1 \right )=1$ 입니다.

 

그리고 구해야하는 답은 $A\left ( N \right )+B\left ( N \right )+C\left ( N \right )$ $mod \left ( 10^{9}+7 \right )$ 입니다.

 

최종 코드는 다음과 같습니다.

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

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

		Matrix Answer;
		for (int i = 0; i < 3; i++) {
			Answer.array[i][0] = 1;
			for (int j = 1; j < 3; j++) {
				Answer.array[i][j] = 0;
			}
		}
		
		Base = matrix_power_modular(Base, N - 1);
		Answer = matrix_multiply_modular (Base, Answer);
		
		long long answer = 0;
		for (int i = 0; i < 3; i++) {
			answer = (answer + Answer.array[i][0]) % mod;
		}
	
		printf("%lld", answer);
	}
	return 0;
}

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

Matrix matrix_power_modular (Matrix Base, long long power) {
	Matrix result;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (j == i) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, Base);
		}
		Base = matrix_multiply_modular (Base, Base);
		power /= 2;
	}
	return result;
}

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

---

12878번과 비슷한 난이도의 문제라고 생각합니다. 그런데 solved ac 레이팅에는 큰 차이가 나는 군요...

 

12878번 문제의 경우는 게시판에서 나온 것과 같이 $N$ 에 대한 일반항을 찾을 수 있었습니다.

 

과연 이 문제에 대해서도 마찬가지일까요?

 

구현은 각자 달랐지만 맞은 사람 1페이지에서는 일반항을 찾은 흔적이 보이지 않는 군요.

 

그 점 또한 이 문제와 12878번의 흥미로운 차이인 것 같습니다.