[BOJ 알고리즘] 1018 "체스판 다시 칠하기"

[BOJ 알고리즘] 1018 "체스판 다시 칠하기"

---

● 문제

• 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

● 소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int main() {

	int n,m;
	scanf("%d %d",&n,&m);
	
	char str[51][51] = {};
	
	for(int i=0; i<n; i++)
	{
		scanf("%s",str[i]);
	}
	
	int answer = 0x2FFFFFFF;
	
	for(int i=0; i<=n-8; i++)
	{
		for(int j=0; j<=m-8; j++)
		{
			int w = 0;
			int b = 0;
			for(int k=0; k<8; k++)
			{
				for(int l=0; l<8; l++)
				{
					if(str[i+k][j+l] == 'B' && (k+l)%2 == 0)
					{
						w++;
					}
					else if(str[i+k][j+l] == 'W' && (k+l)%2 == 1)
					{
						w++;
					}
					
					if(str[i+k][j+l] == 'W' && (k+l)%2 == 0)
					{
						b++;
					}
					else if(str[i+k][j+l] == 'B' && (k+l)%2 == 1)
					{
						b++;
					}
				}
			}
			answer = min(answer,min(w,b));
		}
	}
	printf("%d\n",answer);

	return 0;
}

 

● 풀이

• 특별한 알고리즘은 없다.
• 브루트 포스를 사용하여 모든 8 * 8 경우의 수에 대하여 다시 칠해야 하는 갯수를 세고, 최솟값을 구한다.

 

* www.acmicpc.net/problem/1018 

1018번: 체스판 다시 칠하기