글 읽기 - 1018 C++ 반례 모두 해봤는데 정답으로 나옵니다..ㅠ

dume33 3년 전 0

주석 달아봤습니다. 질문검색을 통해 찾은 여러 반례들 모두 해봐도 모두 정답으로 나오네요... 혹시 발견된 문제점이 있을까요?
#include<iostream>
using namespace std;
#define SIZE 8

void B_recoloring(int**, int**, int, int);
void W_recoloring(int**, int**, int, int);
int cal_min_8x8(int**, int**, int, int);

// nxm의 board배열을 보고 mask배열에 masking작업만 시행(첫 부분이 Black일때)
void B_recoloring(int** board, int** mask, int n, int m) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            mask[i][j] = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] != 1) {
                    mask[i][j] = 1;
                }
            }
            else {
                if (board[i][j] != 0) {
                    mask[i][j] = 1;
                }
            }
        }
    }
}
// nxm의 board배열을 보고 mask배열에 masking작업만 시행(첫 부분이 White일때)
void W_recoloring(int** board, int** mask, int n, int m) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            mask[i][j] = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] != 0) {
                    mask[i][j] = 1;
                }
            }
            else {
                if (board[i][j] != 1) {
                    mask[i][j] = 1;
                }
            }
        }
    }
}

int cal_min_8x8(int** board, int** mask, int n, int m) {
    int min = 1000000;
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n - SIZE + 1; ++i) {  // 큰 size안에서 8x8정사각형 board가 이동
        for (int j = 0; j < m - SIZE + 1; ++j) { // 큰 size안에서 8x8정사각형 board가 이동
            sum1 = 0;
            sum2 = 0;
            int** temp = new int* [SIZE];  // 8x8 이차원배열 생성
            for (int z = 0; z < SIZE; ++z) {
                temp[z] = new int[SIZE];
            }
            if (board[i][j] == 0) {  // 8x8정사각형의 첫 색이 white
                board[i][j] = 1;  // 처음을 black으로 바꿔봄
                for (int k = i; k < i + SIZE; ++k) {  // board에서 8x8사이즈만큼 떼옴
                    for (int l = j; l < j + SIZE; ++l) {
                        temp[k - i][l - j] = board[k][l];  // 8x8만큼 보드에서 떼옴
                    }
                }
                B_recoloring(temp, mask, SIZE, SIZE);  // 완벽한 chess판으로 만들고 수정부분 마스킹
                mask[i][j] = 1;  // 강제로 black으로 바꾼 첫 부분 마스킹
                for (int k = 0; k < SIZE; ++k) {
                    for (int l = 0; l < SIZE; ++l) {
                        sum1 += mask[k][l];  // 수정된 부분 개수 계산
                    }
                }
                board[i][j] = 0;  // 보드 원래대로 되돌려놓음
                temp[0][0] = 0;  // 보드에서 8x8만큼 떼온 것 중 처음 부분만 white로 변경 
                W_recoloring(temp, mask, SIZE, SIZE);
                for (int k = 0; k < SIZE; ++k) {
                    for (int l = 0; l < SIZE; ++l) {
                        sum2 += mask[k][l];  // 수정된 부분 개수 계산
                    }
                }
                int t2_min = sum1 < sum2 ? sum1 : sum2;  // 처음을 바꿀 때와 안바꿀 때 중 작은 것
                min = min < t2_min ? min : t2_min;  // 미니멈 초기화
            }

            else {  // board[i][j] = 1, 8x8정사각형의 첫 색이 black
                board[i][j] = 0;  // 처음을 white로 바꿔봄
                for (int k = i; k < i + SIZE; ++k) {  // board에서 8x8사이즈만큼 떼옴
                    for (int l = j; l < j + SIZE; ++l) {
                        temp[k - i][l - j] = board[k][l];
                    }
                }
                W_recoloring(temp, mask, SIZE, SIZE);  // 완벽한 chess판으로 만들고 수정부분 마스킹
                mask[i][j] = 1;   // 강제로 white으로 바꾼 첫 부분 마스킹
                for (int k = 0; k < SIZE; ++k) {
                    for (int l = 0; l < SIZE; ++l) {
                        sum1 += mask[k][l];  // 수정된 부분 개수 계산
                    }
                }
                board[i][j] = 1;  // 보드 원래대로 되돌려놓음
                temp[0][0] = 1;  // 보드에서 8x8만큼 떼온 것 중 처음 부분만 black로 변경 

                B_recoloring(temp, mask, SIZE, SIZE);
                for (int k = 0; k < SIZE; ++k) {
                    for (int l = 0; l < SIZE; ++l) {
                        sum2 += mask[k][l];  // 수정된 부분 개수 계산
                    }
                }
                int t2_min = sum1 < sum2 ? sum1 : sum2;  // 처음을 바꿀 때와 안바꿀 때 중 작은 것
                min = min < t2_min ? min : t2_min;  // 미니멈 초기화
            } 

            //deallocation
            for (int x = 0; x < SIZE; ++x) {
                delete[] temp[x];
            }
            delete[] temp;
        }
    }

    return min;
}

int main() {
    int n = 0, m = 0;
    cin >> n >> m;
    char c;
    // dynamic allocation
    int** board = new int* [n];
    int** mask = new int* [n];
    for (int i = 0; i < n; ++i) {
        board[i] = new int[m];
        mask[i] = new int[m];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            mask[i][j] = 0;  // 마스킹 배열 초기화
        }
    }
    // 입력받아서 board배열에 B일경우 1로, W일경우 0으로 저장
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> c;
            if (c == 'B') board[i][j] = 1;
            else board[i][j] = 0;
        }
    }
    int res = cal_min_8x8(board, mask, n, m);
    cout << res << endl;

    // deallocation
    for (int i = 0; i < n; ++i) {
        delete[] board[i];
        delete[] mask[i];
    }
    delete[] board;
    delete[] mask;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

1018 C++ 반례 모두 해봤는데 정답으로 나옵니다..ㅠ

dume33 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
