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

#문제

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

1018번: 체스판 다시 칠하기

#풀이

직사각형에 정사각형을 덧대어 두 사각형의 같은 곳과 다른 곳을 어떻게 check할 것인지에 대해 고민해 봐야 한다. 이 문제는 정사각형이 체스판의 형태로 그 무늬가 규칙적이기 때문에 특별한 방법을 생각해 볼 수 있다. 가로의 인덱스와 세로의 인덱스의 합으로 색을 파악할 수 있다는 점에 주목해보자.

또, 이 문제에서 학습할 중요한 점은 2가지 경우 중 1가지 경우를 구하면, 다른 1가지 경우는 간단한 계산을 통해 구할 수 있다는 것을 파악하면 문제가 쉬워진다는 것이다. 왼쪽 위가 흰색인 경우와 검은색인 경우는 정반대의 경우이므로 64에서 한 값을 빼주기만 하면 다른 값을 구할 수 있다.

#소스코드

#include<iostream>
using namespace std;
 
 
int main(void) 
{
    char arr[51][51];
    int cnt = 0;
    int res = 3000;
    int N,M;
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    //입력받기 완료
    
    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
            //8x8의 맨왼쪽위는 arr[i][j]
            cnt = 0;//다시칠해야할 개수
            for (int k = i; k < i + 8; k++) {
                for (int p = j; p < j + 8; p++) {
                    //맨왼쪽위가 W일 때 기준으로
                    if (((k - i) + (p - j)) % 2 == 0) {
                        //W이어야하는 위치
                        if (arr[k][p] != 'W')
                            cnt++;
                    }
                    else {
                        //B이어야하는 위치
                        if (arr[k][p] != 'B')
                            cnt++;
                    }
                }
            }
            if (cnt > 64 - cnt)
                cnt = 64 - cnt;
            if (cnt < res)
                res = cnt;
        }
    }
 
    cout << res;
 
    return 0;
}