체스판 다시 칠하기 (feat. 백준, 1018번)

체스판 다시 칠하기
https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1018
#include <iostream>
#include <cmath>
using namespace std;
char arr[50][50];
int get_min_redraw(register int sx, register int sy) {
	register int check1 = 0, check2 = 0;
	// 좌측 상단이 흰색일 경우 새로 칠해야 하는 개수
	for (register int i = sx, j; i < sx + 8; ++i)
		for (j = sy; j < sy + 8; ++j)
			if ((sx - i) & 1) {			// 행이 홀수일때
				if ((sy - j) & 1) {		// 열이 홀수일때
					if (arr[i][j] != 'W')			++check1;
				}
				else {
					if (arr[i][j] != 'B')			++check1;
				}
			}
			else {
				if ((sy - j) & 1) {		// 열이 홀수일때
					if (arr[i][j] != 'B')			++check1;
				}
				else {
					if (arr[i][j] != 'W')			++check1;
				}
			}
	// 좌측 상단이 검정색일 경우 새로 칠해야 하는 개수
	for (register int i = sx, j; i < sx + 8; ++i)
		for (j = sy; j < sy + 8; ++j)
			if ((sx - i) & 1) {			// 행이 홀수일때
				if ((sy - j) & 1) {		// 열이 홀수일때
					if (arr[i][j] != 'B')			++check2;
				}
				else {
					if (arr[i][j] != 'W')			++check2;
				}
			}
			else {
				if ((sy - j) & 1) {		// 열이 홀수일때
					if (arr[i][j] != 'W')			++check2;
				}
				else {
					if (arr[i][j] != 'B')			++check2;
				}
			}
	return min(check1, check2);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, ans = static_cast<int>(1e9);
	cin >> N >> M;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < M; ++j)
			cin >> arr[i][j];
	for (register int i = 0, j; i <= (N - 8); ++i)
		for (j = 0; j <= (M - 8); ++j)
			ans = min(ans, get_min_redraw(i, j));
	cout << ans << "\n";
	return 0;
}
// *&)*@*

1. 체스판은 좌측 상단이 W인 경우와 B인 경우, 2가지의 경우가 존재합니다.
2. W인 경우, 8X8의 색이 정해져있고 마찬가지로 B인 경우, 8X8의 색이 정해져 있습니다.
3. 따라서 상단 좌측부터 8X8씩 검사하고 그 뒤 좌측으로 한칸씩 검사합니다.
4. 좌측 끝까지 (N-8까지) 검사가 끝났다면 다시 제일 좌측부터 그리고 다음 행부터 끝까지 검사합니다. (M-8까지)