BOJ 9066:: 금고

icpc.me/9066

$A_i$를 처음에 $i$번 칸이 수평이면 $A_i=0$, 수직이면 $A_i=1$로 정의하고, $S_i$를 $i$번 칸을 눌러야 하면 1, 아니면 0으로 정의합시다. 그러면 (2×2인 경우에) 다음이 성립합니다.

\[ \begin{align}
(A_1 + S_1 + S_2 + S_3) \ \% \ 2 &= 0 \\
(A_2 + S_1 + S_2 + S_4) \ \% \ 2 &= 0 \\
(A_3 + S_1 + S_3 + S_4) \ \% \ 2 &= 0 \\
(A_4 + S_2 + S_3 + S_4) \ \% \ 2 &= 0
\end{align} \]

변수($S_1$, $S_2$, …)가 $n^2$개인 연립방정식 $n^2$개가 나오므로, 가우스 소거법으로 풀 수 있습니다. 시간 복잡도는 $O(n^6)$입니다(…)