BOJ 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)$입니다(…)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<bits/stdc++.h> using namespace std; vector<int> gaussian_elim(vector<vector<int>> a, vector<int> b) { int n = a.size(); for (int i = 0; i < n-1; i++) { if (!a[i][i]) { int first; for (first = i+1; first < n && !a[first][i]; first++); assert(first < n); for (int j = i; j < n; j++) swap(a[i][j], a[first][j]); swap(b[i], b[first]); } for (int j = i+1; j < n; j++) if (a[j][i]) { for (int k = i; k < n; k++) a[j][k] = (a[i][k] + a[j][k]) % 2; b[j] = (b[i] + b[j]) % 2; } } for (int i = n-1; i >= 1; i--) for (int j = i-1; j >= 0; j--) if (a[j][i]) { a[j][i] = 0; b[j] = (b[i] + b[j]) % 2; } return b; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t, n; char c; cin >> t; while (t--) { cin >> n; vector<vector<int>> a(n*n, vector<int>(n*n)); for (int i = 0; i < n*n; i++) for (int j = 0; j < n*n; j++) a[i][j] = (i / n == j / n || i % n == j % n)? 1 : 0; vector<int> b(n*n); for (int i = 0; i < n*n; i++) { cin >> c; b[i] = c == 'H'? 0 : 1; } vector<int> x = gaussian_elim(a, b); cout << accumulate(x.begin(), x.end(), 0) << '\n'; } return 0; } |