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

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

 

제출 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<vector<char>> board;
    string array[2][8] = {
        {
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
        },
        {
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
            "BWBWBWBW",
            "WBWBWBWB",
        }};

    int n, m;
    int min = 64;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        string str;
        vector<char> v;
        cin >> str;
        for (int j = 0; j < m; j++)
            v.push_back(str[j]);
        board.push_back(v);
    }

    for (int i = 0; i < n - 7; i++)
    {
        for (int j = 0; j < m - 7; j++)
        {
            int sum[2] = {0};
            for (int a = 0; a < 8; a++)
            {
                for (int b = 0; b < 8; b++)
                {
                    if (board[i + a][j + b] != array[0][a][b]) sum[0]++;
                    if (board[i + a][j + b] != array[1][a][b]) sum[1]++;
                }
            }
            if (sum[0] < min) min = sum[0];
            if (sum[1] < min) min = sum[1];
        }
    }

    cout << min;
}

완벽한 두 가지 경우의 체스판을 미리 선언해 두고 입력으로 들어온 값으로 나올 수 있는 모든 수의 체스판을 돌면서 총 몇 번을 바꿔야 하는지 체크했다

 

for문을 4번 돌게 되지만 n과 m이 최대 50, a와 b는 8씩이므로 시간적으로는 문제가 없으리라 생각했다

(브루트 포스의 경우 연산 횟수가 100,000,000 이하면 시도해볼만 하다고 한다)