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

링크

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

 

풀이

 

 

 

8*8짜리 부분을 선택하고 체스판으로 만들면 되는 문제입니다.

n, m은 50이하이고 자른 체스판은 8*8이기 때문에 모든 수를 고려해도 50*50*8*8로 시간 초과가 나지 않습니다.

(모든 수를 고려하는 걸 Brute-force 알고리즘이라고 합니다.)

 

자른 다음 저 위 두 사진처럼 만들면서 count를 해주면 되는데, 한 경우는 다른 경우의 64-count가 나오기 때문에 하나만 고려해도 됩니다.

 

칠하는 경우는 64가 최대이고, 그걸 고려해서 최소 경우를 찾아주면 됩니다.

 

색을 칠하는 방법은 홀홀과 짝짝은 같은 색, 홀짝과 짝홀은 같은 색이라는 것을 이용해서

(r%2)^(c%2) 이렇게 xor을 해줬습니다.

 

코드

//1018_체스판 다시 칠하기
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, ans=100;
char map[51][51];

int main() {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; ++i) {		//맵 받음
		scanf("\n");
		for (int j = 0; j < m; ++j) {
			scanf("%c", &map[i][j]);
		}
	}

	for (int i = 0; i <= n - 8; ++i) {		//맵 순회
		for (int j = 0; j <= m - 8; ++j) {

			int cnt = 0;
			for (int r = i; r < i + 8; ++r) {		//8*8 맵 받아옴
				for (int c = j; c < j + 8; ++c) {
					if ((r % 2) ^ (c % 2)) {		//짝홀, 홀짝일 때
						if (map[r][c] == 'W') cnt++;	//'W'->'B'
					}
					else { 		//홀홀, 짝짝일 때
						if (map[r][c] == 'B') cnt++;	//'B'->'W'
					}
				}
			}

			ans = min(ans, cnt);		//1
			ans = min(ans, 64 - cnt);	//2
		}
	}

	printf("%d\n", ans);

	return 0;
}