[백준 22021] 자동분무기

22021번: 자동분무기

문제 풀이

처음에는 식 64개, 변수 64개인 방정식을 세워 가우스 소거법으로 풀면 된다고 생각했다.

하지만 이 풀이는 너무 복잡하고 구현이 어렵다. 이 글은 규칙을 찾다가 알게된 방법을 소개한다.

Naive하게 풀 경우

격자는 $N\times N$개, 각 격자 당 . , + , - 로 선택할 수 있다.
이 때 시간복잡도는 $O(N^2\times 3^{N^2})$ 로, $N=8$ 일 때 시간초과가 발생한다.
수학적인 아이디어를 사용해 시간복잡도를 줄여야 한다고 생각했다.

수학적으로 풀 경우

입력값은 $M$, $c[i][j]$ 로 표기하겠다.
$c[i][j]$는 $i$열 또는 $j$행에 있는 (+의 합)-(-의 합)이다.

$sum=$ $\frac{\sum _{j=0}^7\sum _{i=0}^7(c[i][j]-M)}{15}$ 변수를 설정한다.
이 $sum$값은 64개의 격자의 (+의 합)-(-의 합)이다.

자, 그럼 이 코드에서 얻어지는 $judge$는 뭘 뜻할까?

judge = 0;
for (int a = 0; a < 8; a++) {
    for (int b = 0; b < 8; b++) {
        if (a != i && b != j) judge += arr[a][b];
    }
}

정답은 $judge=15sum-(2sum+7arr[i][j])$ 이다.

결론적으로
$13sum-judge+6arr[i][j]$ 값이
양수이면 $ans[i][j]=+$
음수이면 $ans[i][j]=-$
0이면 $ans[i][j]=.$ 이 된다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a; cin >> a;
    int arr[8][8];
    char ans[8][8];
    int sum = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> arr[i][j];
            arr[i][j] = arr[i][j]-a;
            sum += arr[i][j];
            ans[i][j] = '.';
        }
    }
    sum = sum/15;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            int judge = 6*arr[i][j];
            for (int a = 0; a < 8; a++) {
                for (int b = 0; b < 8; b++) {
                    if (a != i && b != j) judge += arr[a][b];
                }
            }
            judge = 13*sum - judge;
            if (judge > 0) ans[i][j]='+';
            if (judge < 0) ans[i][j]='-';
        }
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cout << ans[i][j] << ' ';
        } cout << '\n';
    }
}