백준 26035번: $0101$

 

 

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

26035번: $0101$

---

 

$N$을 편하게 2로 고정해놓고 $M$을 늘리면서 관찰하면 쉬운 문제입니다. 또한, 관찰할 때 저의 경우 위에서부터 1행을 채우고 그 아래 행을 채운다는 느낌으로 접근했습니다.

 

예제에 나온 $M=4$, $N=2$의 경우를 한 번 보게 되면 1행이 $0101$, $1010$일 경우를 제외하고 모두 1행이 정해지면 2행도 단 하나로 결정됐습니다.

 

$M=3$인 경우 $101$, $010$을 제외하고 1행이 정해지면 2행도 하나로 결정됐습니다.

$M=2$일 경우도 마찬가지임을 쉽게 관찰할 수 있습니다.

 

왜 이런 현상이 생길까요?

 

다시 한 번 $M=4$일 때를 관찰해보면, $0101$과 $1010$일 때는 1행과 2행이 동일할 수 있습니다. 그러나, 이를 제외한 1행에 대해서는 반드시 1행과 2행의 모든 자릿수가 서로 달라야 했습니다.

 

즉, 1행의 $M$비트 이진수를 $B_{1}$, 2행의 $M$비트 이진수를 $B_{2}$로 나타냈을 때, 다음이 성립하면 문제의 조건을 만족합니다.

 

$$ B_{1} \wedge B_{2} = 0 $$

(편의상 bitwise and를 $\wedge$로 표기하였습니다.)

 

이때 저 식이 성립하지 않아도 되는 케이스가 바로 $010$, $101$, $0101$, $1010$입니다.

이 케이스들은 $M$비트 이진수 중 MSB부터 LSB까지 0과 1이 번갈아 나오는 것들입니다.

 

그러므로 $2^{M}-2$ 개의 $B_{1}$에 대해 $B_{2}$가 $B_{1} \wedge B_{2} = 0$를 만족하도록 결정되고, 같은 방법으로 $B_{3}$, $B_{4}$ 등 역시 자동으로 결정됩니다.

다시 말해 1행이 $2^{M}-2$ 개 이진수 중 하나로 결정되면 그 자체로 $N \times M$ 배열을 문제의 조건을 만족하도록 채우는 게 됩니다.

 

이제 $0101 \cdots$과 $1010 \cdots$에 대해 생각해보겠습니다.

 

어떤 행이 $0101 \cdots$일 때, 그 아래 행은 $0101 \cdots$ 또는 $1010 \cdots$임을 알 수 있습니다.

마찬가지로 한 행이 $1010 \cdots$이면 그 아래 행은 $1010 \cdots$ 또는 $0101 \cdots$ 입니다.

 

결론적으로 $B_{1}$이 이렇게 0과 1이 교차되는 이진수일 때, $B_{2}$부터 $B_{N}$은 각각 2가지의 경우의 수를 가집니다.

 

이런 점을 고려했을 때 다음 식을 구할 수 있습니다.

 

$$ \textrm{Ans} \left ( N,M \right ) = \left ( 2^{M}-2 \right ) + 2 \times \left ( 2^{N-1} \right ) $$

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

 

위 식을 구현하면 정답을 받을 수 있습니다. 다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000007
 
long long power_modular (long long x, long long y);
 
int main(void) {
 
	long long N, M;
	scanf("%lld %lld", &N, &M);
 
	long long ans = power_modular(2, M) + power_modular(2, N) - 2;
	printf("%lld", ans % mod);
	return 0;
}
 
long long power_modular (long long x, long long y) {
	long long result = 1;
	while (y) {
		if (y % 2) {
			result = result * x % mod;
		}
		x = x * x % mod;
		y /= 2;
	}
	return result;
}

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

---