1. 입력 받는 함수 2. 입력받고 8*8 만 검사하는 함수 3. 몇개의 수정이 필요한지 검사하는 함수를 만듭니다. 여기서 3번 함수인 검사하는 함수에서, 아이디어는 맵의 인덱스의 합이 짝수인지 홀수인지를 검사하여서 원래 체스판의 색이 아니면 modCnt++ 을 하였습니다. 잘라내는 것에서 지난번에 디스플레이에서 불량 화소가 얼마나 나오는지를 알아내는 문제에서 짜 본 적이 있기에 시간을 벌고, 자신감 있게 해결할 수 있었습니다. 풀이 시간 30분 입니다. |
/* 2001 체스판 다시 칠하기 시작. 검은색, 흰색, 8 곱 8 체스판으로 만들고 싶다. 잘라낸 후에 몇 개의 정사각형을 다시 칠하기. 칠해야 하는 보드의 최솟값을 구하는 프로그램을 작성하세요. 체스판은 2 종류 입니다. 1. 입력 받는 함수 2. 입력받고, 8*8로 자르는 함수 왼쪽에서 자르는 경우, 오른쪽에서 자르는 경우, 위에서 자르는 경우, 아래서 자르는 경우 예를 들어서 10, 13 을 받았으면 10-8 = 2 이므로 2 0 1 1 0 2 이렇게 총 3가지 경우의 수가 생깁니다. 오께이 인덱스 어떻게 처리하는지 클리어 여기서, 어느 부분으로 잘라야 하는지 한번 검사해보도록 합니다. 3. 자른 후, 체스판을 만들기 위해 몇개의 수정이 필요한지 검사하는 함수 처음을 받고, 다음것을 받을 때, 달라야 됩니다. 오께이. 두번째 줄을 할 때는, 처음것의 반대여야 합니다. 오께이. 그리고 반대가 아니라면, 반대로 만들고, ++을 해줍니다. 처음 것을 고정시키는 것이 좋을 것 같습니다. 이것은 디버깅 하면서 고 체스판 인지 아닌지 확인하는 함수. */ #include <iostream> #include <algorithm> #include <string> using namespace std; #define SIZE 55 // 55 int map[SIZE][SIZE]; int M, N; int minVal = 2123456789; string str; int moveH; int moveV; int curC; int modCnt; int num = 64; void problemIn() { cin >> M >> N; for (int i = 0; i < M; i++) { cin >> str; for (int j = 0; j < N; j++) { map[i][j] = str[j]; } } } /* 오왼 2 위아래 5 입니다. 그럼 처음에 0,0 0,2 0,4 0,6 은 백색이고, 0,1 0,3 0,5 0,7 은 흑색입니다. 1,0 은 흑색입니다. 짝수는 백색이고, 홀수는 흑색입니다. 반대로도 가능합니다. */ void solve() { // 맵을 이동 시키기
moveH = M - 8; // 10-8 = 2 moveV = N - 8; // 13-8 = 5 for (int k = 0; k < moveH + 1; k++) { for (int k2 = 0; k2 < moveV + 1; k2++) { modCnt = 0; for (int i = k; i < k + 8; i++) { for (int j = k2; j < k2 + 8; j++) { if ((i + j) % 2 == 0 ) { // 짝수인데 그것이 // 이것과 반대? 아니면 if (map[i][j] == 'B') { modCnt++; } } if ((i + j) % 2 == 1) { if (map[i][j] == 'W') { modCnt++; } } } } num = 64; // 여기서 수정하는 것의 크기를 비교해서 두번 검사하지 않도록 합니다. if (modCnt > 32) { modCnt = num - modCnt; } minVal = min(minVal, modCnt); } } } int main() { problemIn(); solve(); cout << minVal << endl; return 0; } |