백준 12878번: Blocks

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

12878번: Blocks

---

우선 이 문제에서 구하고자 하는 경우의 수를 관찰하고자 합니다.

편의상 이하에서 짝수라는 표현을 0을 포함하는 2로 나눠떨어지는 정수들의 집합으로 정의하겠습니다.

 

N개의 블록들을 모두 칠했을 때 빨간색과 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 경우의 수

 

예제를 보면, $N=1$ 일 때 답은 2입니다.

 

전체 블록이 1개이므로 조건을 만족하기 위해 빨간색 또는 노란색으로 칠해진 블록이 0개일 수밖에 없습니다.

 

그렇다면 그 한 개의 블록에 칠할 수 있는 색은 주황색 또는 초록색만 남습니다. 그래서 답은 2입니다.

 

두번째 예제를 보면, $N=2$ 일 때 답은 6입니다.

 

이유를 설명하기 전에 빨강, 주황, 노랑, 초록색으로 칠한 블록의 수를 $\left ( R,O,Y,G \right )$ 으로 나타내겠습니다.

 

$R\sim G$ 는 각각 다음과 같습니다.

 

$R$ 은 빨간색으로 색칠된 블록의 수

$O$ 는 주황색으로 색칠된 블록의 수

$Y$ 는 노란색으로 색칠된 블록의 수

$G$ 는 초록색으로 색칠된 블록의 수

 

이제 $N=2$ 인 경우 두 개의 블록을 색칠할 수 있는 모든 경우의 수를 다음과 같이 생각할 수 있습니다.

 

$\left ( 2,0,0,0 \right ),\left ( 0,2,0,0 \right ),\left ( 0,0,2,0 \right ),\left ( 0,0,0,2 \right )$

$\left ( 1,1,0,0 \right ),\left ( 1,0,1,0 \right ),\left ( 1,0,0,1 \right ),\left ( 0,1,0,1 \right )$

$\left ( 0,1,1,0 \right ),\left ( 0,0,1,1 \right )$

 

그런데, 이 경우 우리가 찾아낸 답은 $\left ( 2,0,0,0 \right ),\left ( 0,0,2,0 \right ),\left ( 0,2,0,0 \right ),\left ( 0,0,0,2 \right ),\left ( 0,1,0,1 \right )$ 입니다.

 

실제 답은 6인데요!

 

그렇다면 $R$ 또는 $Y$가 짝수이면 되는 걸까요? 위 경우의 수에서 그런 조건에 맞게 카운팅하면 9가지가 나옵니다.

게다가 이렇게 가정하게 되면 $N=1$ 일 때도 답이 4가 나오게 됩니다.

 

그래서, 문제에서 요구하는 것은 $R$ 과 $Y$ 가 모두 짝수인 경우의 수라는 것은 확실한데, $N=2$ 일 때의 답을 어떻게 납득할 수 있을까요?

 

제가 내린 결론은, 문제에서 말하는 $N$ 개의 블록은 서로 다른 블록들이라는 것입니다.

 

$N=2$ 일 때 존재하는 블록 2개를 A, B라고 라벨링해보겠습니다.

 

A, B 둘 다를 한 색깔로 칠하는 경우는 물론 색깔별로 한 가지 뿐입니다.

 

그런데, 두 블록 중 하나를 초록색, 하나를 주황색으로 칠하는 경우...

 

A를 주황색으로, B를 초록색으로 칠하는 경우

A를 초록색으로, B를 주황색으로 칠하는 경우

 

이렇게 경우의 수가 갈라집니다!

 

그래서 답이 6이라는 것이 납득됩니다.

 

이제 점화식을 세워볼 차례인데, 그냥 점화식을 세워본다면, 이런 방식을 생각해볼 수 있겠습니다.

 

N개의 블록을 조건을 만족하도록 색칠하는 경우의 수를 $f\left ( N \right )$ 이라 하자.

이때 $f\left ( N \right )$ 과 $f\left ( N+1 \right )$ 의 관계를 구해본다.

 

그런데, 막상 해보면 쉽지 않습니다.

 

우선, $f\left ( 2k+2 \right )$ 에서 얻는 점화관계라면 크게 두 가지가 있겠네요.

 

$\left ( i \right )$ $2k$ 개의 블록을 조건을 만족하도록 칠합니다. 이때 남은 두 개의 블록을 모두 하나의 색깔로 칠하는 방법이 있고, 하나는 주황색으로, 하나는 초록색으로 칠하는 방법이 있습니다.

 

$\left ( ii \right )$ $2k+1$ 개의 블록을 조건을 만족하도록 칠합니다. 이때 남은 하나의 블록은, 초록색 또는 주황색으로 칠해야 합니다.

 

그런데, $2k$ 개의 블록을 색칠했을 땐 조건을 만족하지 않더니 블록 2개를 더 색칠하면 조건을 만족할 수도 있지 않을까요? $2k+1$ 개의 블록에 대해서도 이런 경우가 발생하지 않겠습니까?

 

저는 그런 의혹이 들어 이런 접근을 포기했습니다.

 

어쩌면 $N$ 이 충분히 작은 값일 때, 가령 3, 4 정도일 때의 값을 구해서, 거기서 규칙을 파악하려 해볼 수도 있겠습니다.

 

하지만 그런 방법으로 이 문제를 쉽게 파악하는 것은 저로서는 어려웠습니다.

 

왜 어려웠을까 라는 걸 생각해보면, 이 지점이 문제였던 것입니다.

 

N개의 블록을 조건을 만족하도록 색칠하는 경우의 수를 $\cdots$

 

이제 N개의 블록을 색칠했을 때 나올 수 있는 다음 4가지의 state 들을 생각해보겠습니다.

 

$\left ( a \right )$ $R$ 짝수, $Y$ 짝수

$\left ( b \right )$ $R$ 홀수, $Y$ 짝수

$\left ( c \right )$ $R$ 짝수, $Y$ 홀수

$\left ( d \right )$ $R$ 홀수, $Y$ 홀수

 

즉, 우리가 아까 논의했던 대상인 $f\left ( N \right )$ 은 $\left ( a \right )$ 에 해당함을 알 수 있습니다.

 

$\left ( a \right )\sim\left ( d \right )$ 을 함수의 꼴로 잘 정의해 봅시다.

 

$N$ 개의 블록을 $R$ 과 $Y$ 가 모두 짝수가 되도록 색칠하는 경우의 수 $A\left ( N \right )$

$N$ 개의 블록을 $R$ 은 홀수, $Y$ 는 짝수가 되도록 색칠하는 경우의 수 $B\left ( N \right )$

$N$ 개의 블록을 $R$ 은 짝수, $Y$ 는 홀수가 되도록 색칠하는 경우의 수 $C\left ( N \right )$

$N$ 개의 블록을 $R$ 과 $Y$ 가 모두 홀수가 되도록 색칠하는 경우의 수 $D\left ( N \right )$

 

이제 $N$ 개의 블록과 $N+1$ 개의 블록의 관계에 대해서 생각해봅시다.

 

$N$ 개의 블록을 색칠 했을 때 $\left ( a \right )$ 였습니다.

 

이때 $N+1$ 번째의 블록을

 

빨간색으로 색칠하면, 새로운 상태 $\left ( b \right )$ 가 됩니다.

노란색으로 색칠하면, 새로운 상태 $\left ( c \right )$ 가 됩니다.

주황색이나 초록색으로 색칠하면, 새로운 상태 $\left ( a \right )$ 가 됩니다.

 

$N$ 개를 색칠하여 $\left ( a \right )$ 인 것과 $N+1$ 개를 색칠하여 $\left ( a \right )$ 인 것을 같게 볼 수는 없기 때문입니다.

 

이제 앞서 정의했던 $A\left ( N \right )\sim D\left ( N \right )$ 의 점화식을 찾을 수 있습니다.

 

위에서 $\left ( a \right )$ 에게 시행했던 것과 마찬가지로 반복한 것을 정리해보면 다음과 같습니다.

 

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

$B\left ( N+1 \right ) = A\left ( N \right ) + 2\times B\left ( N \right ) + D\left ( N \right )$

$C\left ( N+1 \right ) = A\left ( N \right ) + 2\times C\left ( N \right ) + D\left ( N \right )$

$D\left ( N+1 \right ) = B\left ( N \right ) + C\left ( N \right ) + 2\times D\left ( N \right )$

 

이를 행렬로 옮기는 것은 간단합니다. 다음과 같이 옮기면 충분합니다.

 

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

 

마지막 단계입니다.

 

최종적으로 우리는 이 식을 얻었으니, $A\left ( 1 \right )\sim D\left ( 1 \right )$ 을 구하면 됩니다.

 

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

 

정의에 따라 각각의 값을 구하면 다음과 같습니다.

 

$A\left ( 1 \right ) = 2$

$B\left ( 1 \right ) = 1$

$C\left ( 1 \right ) = 1$

$D\left ( 1 \right ) = 0$

 

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

#include <stdio.h>
#define mod 10007

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

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

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

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result = { {{0}} };
	for (int i = 0; i < 4; i++) {
		for (int k = 0; k < 4; k++) {
			for (int j = 0; j < 4; j++) {
				int 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, int power) {
	Matrix result = { {{0}} };
	for (int i = 0; i < 4; i++) {
		result.array[i][i] = 1;
	}
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, Base);
		}
		Base = matrix_multiply_modular (Base, Base);
		power /= 2;
	}
	return result;
}

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

 

이 풀이는 다음 링크에서 접했습니다. ( https://js1jj2sk3.tistory.com/110 )

---

백준 게시판에 따르면 조합론적 풀이가 하나 더 있습니다. ( https://www.acmicpc.net/board/view/26769 )

 

이 풀이는 $N$ 개의 블록에 대해 $R$ 과 $Y$ 가 모두 2로 나눠 떨어질 때, $R + Y$ 의 값을 기반으로 접근합니다.

 

$\left ( i \right )$ $R+Y$ 는 0일 수 있습니다. $R=Y=0$ 이므로, $N$ 개의 블록은 색을 두 가지 선택할 수 있습니다.

 

따라서 이때의 경우의 수는 $2^{N}$ 입니다.

 

$\left ( ii \right )$ $R+Y$ 가 자연수 $k$ 에 대해 $R+Y=2k$ 로 나타나는 경우를 생각해 봅시다. (단, $2k\leq N$ )

 

$\left ( a \right )$ $N-2k$ 개의 블록은 색을 두 가지 선택할 수 있습니다.

 

$\left ( b \right )$ $N$ 개의 서로 다른 블록 중에, $2k$ 개의 블록을 선택합니다.

 

$\left ( c \right )$ 선택된 $2k$ 개의 서로 다른 블록들에 대해 다음 경우들을 모두 고려해야 합니다.

 

$2k$ 개의 블록 중 0개가 빨간색으로, $2k$ 개가 노란색으로 색칠되는 경우

$2k$ 개의 블록 중 2개가 빨간색으로, $2k-2$ 개가 노란색으로 색칠되는 경우

$\vdots$

$2k$ 개의 블록 중 $2k-2$ 개가 빨간색으로, 2개가 노란색으로 색칠되는 경우

$2k$ 개의 블록 중 $2k$ 개가 빨간색으로, 0개가 노란색으로 색칠되는 경우

 

따라서 이때의 경우의 수는 $2^{N-2k}\times \binom{N}{2k}\times \left ( \binom{2k}{0} + \binom{2k}{2} + \cdots + \binom{2k}{2k-2} + \binom{2k}{2k} \right )$ 입니다.

 

한편 이항정리에 따르면 $\left ( \binom{2k}{0} + \binom{2k}{2} + \cdots + \binom{2k}{2k-2} + \binom{2k}{2k} \right )=2^{2k-1}$ 입니다. 증명은 이 글에서 생략하겠습니다. 

 

따라서 경우의 수는 $2^{N-2k}\times \binom{N}{2k}\times 2^{2k-1}=2^{N-1}\times \binom{N}{2k}$ 입니다.

 

이제 $2k=2,4,6,\cdots,2\left \lfloor \frac{N}{2} \right \rfloor$ 에 대해 위 식의 값을 모두 더해주면 됩니다.

 

따라서 경우의 수는 $2^{N-1}\times \sum _{k=1}^{\left \lfloor \frac{N}{2} \right \rfloor} \binom{N}{2k}$ 입니다.

 

$\left ( iii \right )$ 재밌는 것은, $\left ( ii \right )$ 의 최종 식을 $k=0$ 까지 확장시킨 결과입니다.

 

$2^{N-1}\times \sum _{k=1}^{\left \lfloor \frac{N}{2} \right \rfloor} \binom{N}{2k}=2^{N-1}\times \left \{ \left ( \sum _{k=0}^{\left \lfloor \frac{N}{2} \right \rfloor} \binom{N}{2k} \right )-1 \right \}=\left ( 2^{N-1}\times \sum _{k=0}^{\left \lfloor \frac{N}{2} \right \rfloor} \binom{N}{2k} \right )-2^{N-1}$

 

또 이항정리에 따르면 $\sum _{k=0}^{\left \lfloor \frac{N}{2} \right \rfloor} \binom{N}{2k}=2^{N-1}$ 이므로...

 

$\left ( ii \right )$ 에서 구했던 경우의 수가 결국 다음과 같습니다.

 

$2^{N-1}\times 2^{N-1} - 2^{N-1} = 2^{2N-2} - 2^{N-1}$

 

이를 $\left ( i \right )$ 에서 구했던 경우의 수와 합쳐서, 이 문제에서의 $N$ 에 대한 일반항이 나옵니다!

 

$2^{N}+2^{2N-2}-2^{N-1}=2^{N-1}+2^{2N-2}$

 

실제로, $N=1$ 일 때, $N=2$ 일 때, 모두 예제의 답과 일치하는 것을 확인할 수 있습니다.

 

이 아이디어를 활용한 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 10007

int expof2 (int X);

int main() {
    
    int N;
    scanf("%d", &N);
    
    int answer = (expof2(N-1) + expof2(2*N-2)) % mod;
    printf("%d", answer);
    
    return 0;
}

int expof2 (int X) {
    int result = 1, base = 2;
    while(X) {
        if (X % 2) {
            result = result * base % mod;
        }
        base = base * base % mod;
        X /= 2;
    }
    return result;
}

(C11, 1112KB, 0ms, 제출번호 31105083)

 

역시 조합론적인 풀이는 아름답지만 그만큼 발상이 어려운 것 같습니다.

 

게시판을 보기 전까지는 상상도 못했던 풀이였습니다.

---