[백준] 1018번 : 체스판 다시 칠하기

문제

 

---

풀이

 

커다란 체스판을 8x8 체스판으로 만들 수 있는 모든 경우의 수에 대해 계산한다. 체스판을 자르고, 편의상 왼쪽 맨위칸은 흰색으로 시작한다고 가정한다. 바꿔야 할 칸의 수를 계산했다면 이게 32보다 큰지 확인해야 한다. 만약 32칸보다 많이 바꿔야 한다면, 그냥 반대로 칠하는게 더 나았던 상황인 것이다. 아무튼 이런식으로 각 부분 체스판마다 바꿔야 하는 칸 수를 세고 최솟값을 갱신하면 된다.

---

소스코드

 

#include <iostream>
using namespace std;

int main() {
	int N, M, i, j, a, b, fix, min_fix = 65;

	cin >> N >> M;
	char** panel = new char* [N];
	for (i = 0; i < N; i++)
		panel[i] = new char[M];
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			cin >> panel[i][j];
		}
	}
	for (i = 0; i <= N - 8; i++) { //8x8 만들 수 있는지 봐야함
		for (j = 0; j <= M - 8; j++) {
			fix = 0;
			for (a = i; a < i + 8; a++) {
				for (b = j; b < j + 8; b++) {
					if (((a + b) % 2 == 0) && (panel[a][b] == 'B')) //B를 W로 바꿈
						fix++;
					if (((a + b) % 2 == 1) && (panel[a][b] == 'W')) //W를 B로 바꿈
						fix++;
				}
			}
			if (fix > 32) //바꾸고 보니 반대로 바꾸는게 더 나을듯
				fix = 64 - fix;
			if (min_fix > fix) //지금까지 바꾼 것 중에 제일 낫나?
				min_fix = fix;
		}
	}
	cout << min_fix << endl;
}