백준 1018 체스판 다시 칠하기 - C++

 

접근

어떠한 M*N크기의 판이 있을 때 이 판을 8*8로 자를 수 있는 모든 경우의 수를 구한다.

각각의 8*8로 잘려진 판을 체스판으로 만들 때 다시 칠해야 하는 최소비용을 구해야 한다. 

어떻게 구해야 할까?

우선,  체스판이 될 수 있는 조건은 맨 처음 칸 색깔이 검은색일 수도 있고 흰색일 수도 있다.

축소해서 생각해보자 체스판이 4*4라 했을때 

WBWB    BWBW    

BWBW    WBWB

WBWB    BWBW

BWBW    WBWB

위와 같이 두가지가 나올 수 있다.

 

그렇다면 잘려진 판에서 맨 처음이 흰색으로 시작하는 체스판 그리고 검은색으로 시작하는 체스판 각각의 비용을 비교해 더 작은 값이 최소 값이 된다.

#include <iostream>
#include <string>
using namespace std;
string chess[50];
int findMin(int low, int col){
    char clr = 'W';
    int wCnt = 0;
    // 맨 처음이 흰색 시작
    for(int i=low; i<low+8; i++){
        clr = ( i%2 == 0 ) ? 'W' : 'B';
        for(int j=col; j<col+8; j++){
            if(chess[i][j] != clr) wCnt++;
            clr = (clr == 'W') ? 'B' : 'W';
        }
    }
    int bCnt=0;
    // 맨 처음이 검은색 시작
    for(int i=low; i<low+8; i++){
        clr = ( i%2 == 0 ) ? 'B' : 'W';
        for(int j=col; j<col+8; j++){
            if(chess[i][j] != clr) bCnt++;
            clr = (clr == 'W') ? 'B' : 'W';
        }
    }
    
    return wCnt <= bCnt ? wCnt : bCnt;
}

int main()
{
    int N,M;
    cin >> N >> M;
    int minCnt = 8*8;
    for(int i=0; i<N; i++){
        cin >> chess[i];
    }
    for(int low=0; low<=N-8; low++){
        for(int col=0; col<=M-8; col++){
            int t = findMin(low,col);
            if(minCnt > t) minCnt = t;
        }
    }
    cout << minCnt << '\n';
    return 0;
}

8*8판에서 index 기준으로 index%2의 나머지가 0인 것은 0,2,4,6에 해당한다.

이 것을 이용하여 첫 번째 색이 흰색으로 시작할지 검정색으로 시작할지 판단할 수 있다.

minCnt가 처음에 8*8인 이유는 최악의 경우 체스판 전체를 다시 색칠해야 할 수도 있기 때문이다.