02.07. 체스판 다시 칠하기[Brute-force Search][백준 1018]

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

1018번: 체스판 다시 칠하기

 

Algorithm classification : Brute-force Search

 

02.07.1. Problem

Jimin found an M×N board divided into MN unit squares in his mansion. Some squares are painted black, others are painted white. Jimin wants to cut this board and make it into an 8x8 chessboard.

 

The chessboard should be painted black and white alternately. Specifically, each cell must be colored in either black or white, and the two rectangles sharing a side must be colored in a different color. So, according to this definition, there are only two cases of coloring a chessboard. One is when the top left corner is white, and the other is when it is black.

 

There was no guarantee that the board was painted like a chessboard, so Jimin decided to repaint a few squares after cutting it into an 8x8 chessboard. Of course, you can choose the 8*8 size anywhere. Write a program to find the minimum number of squares that Jimin needs to repaint.

 

02.07.2. Input limit

N and M are given in the first line. N and M are natural numbers greater than or equal to 8 and less than or equal to 50. From the second row to the N rows, the status of each row of the board is given. B is black and W is white.

 

02.07.3. Output

The first line prints the minimum number of squares that Jimin needs to repaint.

 

02.07.4. Solution

입력의 최대치는 50by50입니다. 체스판의 크기는 8by8이죠. 모든 위치를 다 고려하면 됩니다.

	int m, n, i, j, k, r, ans = 64, temp1, temp2;
	scanf("%d %d", &n, &m);
	
	char data[n][m];
	for(i = 0; i < n; i++)
		scanf("%s", data[i]);
	for(i = 0; i <= n-8; i++){
		for(j = 0; j <= m-8; j++){
			temp1 = temp2 = 0;
			for(k = i; k <= i+7; k++){
				for(r= j; r <= j+7; r++){
					if(((k+r)%2 == 0 && data[k][r] - 'W' ) || ((k+r)%2 == 1 && data[k][r] - 'B' ))
						temp1++;
					if(((k+r)%2 == 0 && data[k][r] - 'B' ) || ((k+r)%2 == 1 && data[k][r] - 'W' ))
						temp2++;
				}
			}
			temp1 = min(temp1, temp2);
			ans = min(ans, temp1);
		}
	}

	printf("%d",ans);

보시면 아시겠지만 indexing만 잘하면 됩니다. 포인트는 아래의 표로 이해하시면 됩니다.

	0	1	2
0	0+0 = 0	1+0 = 1	2+0 = 2
1	0+1 = 1	1+1 = 2	2+1 = 3
2	0+2 = 2	1+2 = 3	2+2 = 4

감이 오시나요 굵게 배경처리한 부분은 index의 합이 짝수임을 알 수 있습니다. 주의할 점은 이부분이 W인게 최적일 수도 있고 B인게 최적일 수도 있겠죠. 그 Case를 나누어야 한다는 것입니다. 포스팅하면서 한 생각인데 굳이 Case를 나누지 않고 하나의 경우에 대해서만 계산하고 그 값을 temp라 한다면 64-temp와 비교해서 최소값을 ans에 업데이트 해주는 방식도 괜찮겠네요. 한번 temp1과 temp2의 합을 출력해보니 다 64가 나오네요..아... 뺄셈 한번하면 될걸 시간을 더 사용했군요.