1018 - 체스판 다시 칠하기

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

#include <iostream>
using  namespace std;
int main(){

    int n, m;
    cin >> n >> m;
    char row_W[1][8] = {'W','B','W','B','W','B','W','B'};
    char row_B[1][8] = {'B','W','B','W','B','W','B','W'};
    char f[51][51];
    for(int i = 0; i < n; i++){
        cin >> f[i];
    }

    int min = 50000000;



    for(int i = 0; i < n; i++){
        int count = 0;
        for(int j = 0; j < m; j++){
            int sum = 0;
            if(i+7 < n && j+7 < m){
                for(int k = i; k <= i+7; k++){
                    int index = 0;
                    count = 0;
                    for(int z = j; z <= j+7; z++){
                        if(f[i][j] == 'W'){
                            if((k-i) % 2 == 0){
                                if(f[k][z] != row_W[0][index]) count++;
                             }
                            else if((k-i) % 2 != 0){
                                if(f[k][z] != row_B[0][index]) count++;
                            }
                        }else if(f[i][j] == 'B'){
                            if((k-i)%2 == 0){
                                if(f[k][z] != row_B[0][index]){
                                    count++;
                                }
                            }
                            else if((k-i) % 2 != 0){
                                if(f[k][z] != row_W[0][index]) {
                                    count++;
                                }
                            }
                        }
                        index++;
                    }
                    sum+=count;
                }
                if(min > sum) min = sum;
            }
        }
    }

    cout << min;

    return 0;
}

 

for문을 돌면서 좌측상단의 값을 시작으로 그에 맞는 row 배열을 사용하여 한줄한줄 비교하면서 틀린 개수를 세려고했다

8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

하지만 이러한 반례가 존재했고 위의 테스트케이스에선 첫번째의 원소 B만 W로 바꿔주면 W로 시작하는 체스판을 완성할수 있는데

 

나의 소스코드로는 B로 시작하는 체스판을 만들기 시작하면서 63번을 다시 수정해버려야 했다.

 

같이 풀었던 형의 도움을 받아 아예 가능한 체스판 2개를 만들고 그 체스판을 비교하면 확실하게 최소값을 구할수 있었다.

#include <iostream>
using  namespace std;
int main(){

    int n, m;
    char f[51][51];
    // 체스판 1
    char check1[8][8] = {{'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},};

    //체스판 2
    char check2[8][8] = {{'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},
                         {'B','W','B','W','B','W','B','W'},
                         {'W','B','W','B','W','B','W','B'},};
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> f[i];
    }

    int min_value = 50000000; // 최대 고쳐야하는 횟수를 50*50이라고 생각하고 2500보다 큰수 아무거나



    for(int i = 0; i < n; i++){ // ---> 1번 for문
        for(int j = 0; j < m; j++){ // ---> 2번 for문
            int sum1 = 0;
            int sum2 = 0;
            if(i+7 < n && j+7 < m){
                for(int k = i; k <= i+7; k++){ // ---> 3번 for문
                    for(int z = j; z <= j+7; z++){ // ---> 4번 for문
                        if(check1[k-i][z-j] != f[k][z]) sum1++;
                        if(check2[k-i][z-j] != f[k][z]) sum2++;
                    }
                }
                int result = min(sum1,sum2);
                min_value = min(result,min_value);
            }
        }
    }

    cout << min_value << '\n';

    return 0;
}

체스판 1, 2를 동시에 비교하며 체스판 1일때 수정한횟수와 체스판 2일때 수정한횟수 중 최소값을 선택한다.

 

시간복잡도는 50*50*64 대략 16만정도된다 처음엔 for문이 4개를 사용해야하길래 시간초과일까 생각했지만

 

3,4번 for문을 생각보다 많이 사용하지않아서 만약 사용해도 2초(2억)안에 들기때문에 시간초과가 날 경우는 없었다.

 

3시간 정도를 풀었던문제다 징징대지말자