취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2514번 문제인 자동분무기이다.
문제는 아래 링크를 확인하자.

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

가장 먼저 떠오른 풀이는 64개의 변수로 이루어진 연립방정식을 푸는 것이다. 이것은 가우스 소거법(Gaussian Elimination)을 이용하면 구현할 수 있다. 이 글에서는 다른 풀이를 소개한다.

i행 j열에 있는 칸의 생산증감량을 Sij라 하고, Aij를 해당 칸에 설치된 (비료액/제초제/설치안됨)에 따라 각각 (1/-1/0)이라고 하자. 이 때 Sij는 i행에 있거나 j열에 있는 A값들의 합, 즉 모든 Aik와 Akj들의 합이 된다(Aij는 한 번만 더한다).

이제, i행의 모든 S를 더한 값과 j열의 모든 S를 더한 값을 합치면 2(모든 Aij들의 합) + 7Sij + 7Aij가 나온다는 것을 알 수 있다. 이해가 잘 안 된다면 그림을 그려 색칠해보자.

모든 Aij들의 합은 모든 Sij들의 합을 15로 나누어 구할 수 있다. 각 Aij는 i행 또는 j열의 A값을 포함하고있는 15개의 S값에 포함되어 있기 때문이다.

위 식을 적절히 이항하여 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[8][8];
int rsum[8];
int csum[8];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int total = 0;
	int N, K; cin >> N >> K;
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 8; c++) {
			int& x = arr[r][c];
			cin >> x;
			x -= N;
			total += x;
			rsum[r] += x;
			csum[c] += x;
		}
	}

	total /= 15;
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 8; c++) {
			int x = -(2 * total + 7 * arr[r][c] - rsum[r] - csum[c]) / 7;
			if (x == 1) cout << '+' << ' ';
			else if (x == -1) cout << '-' << ' ';
			else cout << '.' << ' ';
		}
		cout << '\n';
	}
}