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

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 N과 M이 주어진다. M과 N은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개 줄에는 체스판의 색 상태가 주어진다. B는 검정색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

소스코드

#include <iostream>
#include <string>
using namespace std;
string board[50];
int n, m;
int countDrawing(int y, int x)
{
	int cnt1 = 0, cnt2 = 0, ret;
	for (int i = y; i < y + 8; i++)
	{
		for (int j = x; j < x + 8; j++)
		{
			if ((i - y + j - x) % 2 == 0)
			{
				if (board[i][j] == 'B')
					cnt1++;
			}
			else
			{
				if (board[i][j] == 'W')
					cnt1++;
			}
		}
	}
	for (int i = y; i < y + 8; i++)
	{
		for (int j = x; j < x + 8; j++)
		{
			if ((i - y + j - x) % 2 == 0)
			{
				if (board[i][j] == 'W')
					cnt2++;
			}
			else
			{
				if (board[i][j] == 'B')
					cnt2++;
			}
		}
	}
	ret = cnt1 < cnt2 ? cnt1 : cnt2;
	return ret;
}
int main(void)
{
	int cnt = 0, min = 65;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> board[i];

	for (int y = 0; y <= n - 8; y++)
	{
		for (int x = 0; x <= m - 8; x++)
		{
			cnt = countDrawing(y, x);
			if (min > cnt)
				min = cnt;
		}
	}
	cout << min;
}

Tip

8*8로 잘라가면서 체스판을 다시 칠해가면서 답을 구한다. 그리디 알고리즘으로 해결이 가능.