[백준] 1018번 체스판 다시 칠하기 (C)

문제 주소

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

1018번: 체스판 다시 칠하기

알고리즘

브루트 포스

힌트

정답 배열을 만들어 놓고 비교한다.

 

 

풀이

B와 W가 반복해서 나와야 하는데 B가 먼저 올 수 도 있고 W가 먼저올 수도 있다. 이것을 따로 계산해주면 복잡해서 W가 먼저 나온다고 가정을 하고 문제를 푼다. 이 때 색을 칠하는 개수와 64 - 색을 칠하는 개수중 더 작은 수가 색을 칠하는 최소 개수가 된다. 64 - 색을 칠하는 개수가 B가 먼저 나올 경우를 생각해 주는 것이다.

#include<iostream>
#include<string>
using namespace std; 
string in[50];
string chess[8]={"WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"};
int main(){
    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    //cout<<"d";
    int ans=64;
    for(int i=0;i<=n-8;i++){
        for(int j=0;j<=m-8;j++){
            int cnt=0;
            for(int k=i;k<i+8;k++){
                for(int l=j;l<j+8;l++){
                    if(in[k][l]!=chess[k-i][l-j])
                        cnt++;
                }
            }
            cnt=min(cnt,64-cnt);
            ans=min(ans,cnt);
        }
    }

    cout<<ans;
}