1018: 체스판 다시 칠하기

-Class2: Silver 5

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

1018번: 체스판 다시 칠하기

 

-결과

 

-코드

#include <stdio.h>

int main(){
    int row, col; //체스판의 가로, 세로
    char array[50][50];
    int min = 32; 
    
    scanf("%d %d", &row, &col);
    
    for(int i = 0; i < row; i++){
        scanf("%s", array[i]);
    }
    
    for(int i = 0; i < row - 7; i++){ //세로 범위
        for(int j = 0; j < col - 7; j++){ //가로 범위
            int count = 0;
            for(int s_i = i; s_i < i + 8; s_i++){
                for(int s_j = j; s_j < j + 8; s_j++){
                    count += (s_i + s_j) % 2 == 1 ^ array[s_i][s_j] == 'B'; 
                }
            }
            count = 64 - count < count ? 64 - count : count;
            min = count < min ? count : min;
        }
    }
    
    printf("%d\n", min);
    return 0;
}

 

-풀이

M*N 크기의 체스판을 모두 돌면서 다시 칠해야 하는 정사각형의 수가 최소인 경우를 찾는 문제이다.

맨 왼쪽 위칸을 흰색으로 가정하고 계산하면, 0,0은 흰색, 0,1은 검정색, 1,0은 검정색, 1,1은 흰색이 된다. 즉, 가로 세로 인덱스의 합이 짝수이면 흰색, 홀수이면 검정색이 들어간다. 따라서 합과 들어있는 색이 잘못된 경우를 카운트하면 다시 칠해야 하는 칸의 개수가 나온다. 이 계산을 반복하고 그 중 최소값을 구하여 출력하면 된다.