백준 1018_체스판 다시 칠하기

 

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

1018번: 체스판 다시 칠하기

8X8의 크기로 잘라 색칠할떄 가장 효율적인 방법을 구하는 문제

#include <iostream>
using namespace std;


int main()
{
	char n[50][50];
	int x = 0, y = 0;
	cin >> x >> y;
	for (int i = 0; i < x; i++)
	{
		string a;
		cin >> a;
		for (int iq = 0; iq < y; iq++)
		{
			n[i][iq] = a[iq];
		}
	}
	x -= 8;
	y -= 8;
	int bcount=0;
	int wcount=0;
	int ans=32;
	for (int i = 0; i <= x; i++)
	{
		for (int iq = 0; iq <= y; iq++)
		{
			for (int z = 0; z < 8; z++)
			{
				for (int iz = 0; iz < 8; iz++)
				{
					if ((z + iz) % 2 == 0)
					{
						if (n[z + i][iz + iq] == 'B')
						{
							bcount += 1;
						}
						else
						{
							wcount += 1;
						}
					}
					else
					{
						if (n[z + i][iz + iq] == 'W')
						{
							bcount += 1;
						}
						else
						{
							wcount += 1;
						}
					}
				}
			}
			if (ans>bcount)
			{
				ans = bcount;
			}
			if (ans>wcount)
			{
				ans = wcount;
			}
			bcount = 0;
			wcount = 0;
		}
		
	}
	cout << ans;
}

검정부터 시작하는 경우 흰색부터 시작하는 경우 2가지를 비교해가며 가장 효율적인 방법을 찾음

 

결과