BOJ 1018번 :: 체스판 다시 칠하기

#문제

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

1018번: 체스판 다시 칠하기

 

#작성 코드

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int min(int a, int b){
	return a<b?a:b;
}

int calCnt(const char board[52][52], int i, int j) {
	int cnt = 0;					// 새로 칠해야 할 칸의 개수 
	for (int p = 0; p<8; p++) {
		for (int q = 0; q<8; q++) {
			if( p%2==0 ){
				if( q%2==0 ){
					if( 'B' == board[i+p][j+q])
						cnt++;
				}
				else{
					if( 'W' == board[i+p][j+q])
						cnt++;
				}
			}
			else{
				if( q%2==0 ){
					if( 'W' == board[i+p][j+q])
						cnt++;
				}
				else{
					if( 'B' == board[i+p][j+q])
					cnt++;
				}
			}
		}
	}
	return cnt;
}

char board[52][52];

int main() {
	int N, M;
	cin>>N>>M;

	// 주어진 보드의 상태 입력!!! 
	for (int i = 1; i<=N; i++) {
		for(int j=1; j<=M; j++)
			cin>>board[i][j];
	}

	int Min = 3000;	// 새로 칠해야하는 칸의 최소 개수
	for (int i = 1; i<=N-7; i++) {
		for (int j = 1; j<=M-7; j++) {
			int cnt = calCnt(board, i, j);
			cnt = min(cnt, 64-cnt);
			Min = min(Min, cnt);
		}
	}
	printf("%d\n", Min);
	return 0;
}

2020/02/06 review

#include <iostream>
using namespace std;
 
int answer=1000000;
char chess[50][50];
 
int main(){
    int size1, size2;
    cin>>size1>>size2;
    for(int i=0; i<size1; i++){
        for(int j=0; j<size2; j++){
            cin>>chess[i][j];
        }
    }
 
    for(int x=0; x<size1-7; x++){
        for(int y=0; y<size2-7; y++){
            int cnt=0;
            for(int sizex=0; sizex<8; sizex++){
                for(int sizey=0; sizey<8; sizey++){
                    if( x+sizex >= size1 || y+sizey >=size2 )
                        continue;
                        
                    if( (x+y+sizex+sizey)%2==0 ){
                        if( chess[x+sizex][y+sizey]=='W' ){
                            cnt++;
                        }
                    }
                    else if( (x+y+sizex+sizey)%2!=0 ){
                        if( chess[x+sizex][y+sizey]=='B'){
                            cnt++;
                        }
                    }
                }
            }
            cnt = min(cnt, 64-cnt);
            answer = min(answer, cnt);
        }
    }
    cout<<answer<<'\n';
    return 0;
} 

 

##

https://www.acmicpc.net/board/view/38392에서 반례를 찾아서 코드를 수정했다.

이상하게도, 당연히 주어진 체스판의 첫 번째 칸을 기준으로 8*8만큼을 비교해야 한다고 생각했다.

8*8만큼 자르는 것을 기준으로 첫 번째 칸과 비교해서 고쳐야 할 칸 수(cnt)를 세었을 때

흰색으로 시작하는 값을 기준으로 생각했다면, 검은색 칸으로 시작할 때는 64-cnt 만큼만 칸을 고쳐주면 된다.

고쳐야 할 칸의 최솟값은 흰색으로 시작하는 보드, 검은색으로 시작하는 보드 두 케이스 모두를 고려한 값 중에서 더 작은 값을 선택하면 되는 것이었다.