[C++] 1018번 체스판 다시 칠하기 - 문제풀이

● 문제 접근 과정

1. 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
2. 일단 어디든 잘라서 8*8로 가장 적은 정사각형을 칠하면 된다.
3. W로 시작하는 패턴 B로 시작하는 패턴을 잡아준다.
4. WB cnt는 W로 시작하는 패턴 BW cnt는 B로 시작하는 패턴을 찾아 카운팅 해주는 함수다.
5. 두개의 함수의 리턴값을 기준으로 처음부터 끝까지 중에서 가장 적은 정사각형을 그리는 cnt를 cout 해준다.

● 구현

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
using namespace std;
string WB[8] = {"WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW",
                "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW"};
string BW[8] = {"BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB",
                "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB"};
string board[50];
int WB_cnt(int x, int y) {
  int cnt = 0;
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      if (board[x + i][y + j] != WB[i][j])
        cnt++;
    }
  }
  return cnt;
}
int BW_cnt(int x, int y) {
  int cnt = 0;
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      if (board[x + i][y + j] != BW[i][j])
        cnt++;
    }
  }
  return cnt;
}
int main() {
  int min_val = 12345;
  pair<int, int> p1;
  cin >> p1.first >> p1.second;
  for (int i = 0; i < p1.first; i++)
    cin >> board[i];
  for (int i = 0; i + 8 <= p1.first; i++) {
    for (int j = 0; j + 8 <= p1.second; j++) {
      int tmp;
      tmp = min(WB_cnt(i, j), BW_cnt(i, j));
      if (tmp < min_val) {
        min_val = tmp;
      }
    }
  }
  cout << min_val;
  return 0;
}

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

1018번: 체스판 다시 칠하기