[백준 알고리즘] 1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

풀이방법:    

 

1) 체스판 8*8 크기로 자르기

지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다.

-> 8*8 크기의 체스판을 잘라서 바꿔야 하는 칸만 바꿈

2) 화이트로 판이 시작했을 때, 블랙으로 판이 시작했을 때 나눠서 바꿔야 하는 칸의 수 세기

블랙으로 판이 시작됐다고 하자.

그렇다면 i와 j를 더한 값이 짝수인 경우에 B, 홀수인 경우에 W가 와야 한다. 

 i와 j를 더한 값이 짝수인 경우에 W, 홀수인 경우에 B가 왔을 때 count를 더해 준다. ( 화이트로 판이 시작했을 때에도 마찬가지 )

// 블랙으로 판이 시작할 때
                    if((k+p)%2 == 0 && input_chess[k][p] == 'W'){
                        bcount ++;
                    }else if((k+p)%2 == 1 && input_chess[k][p] == 'B'){
                        bcount ++;
                    }

3) count 최솟값 찾기

지금까지 count된 값 중에 제일 작은 값이 min_color_change이고, 만약 이것보다 작은 값이 count가 된다면 min_color_change의 값을 바꾼다.

 

if( min_color_change > wcount){
     min_color_change = wcount;
}
if( min_color_change > bcount){
     min_color_change = bcount;
}

 

작성한 코드는 다음과 같다. 

#include <iostream>
using namespace std;

int main() {
    int N,M;
    cin >> N >> M;
    char input_chess[N][M];
    int min_color_change = 100;
   
    for(int i = 0; i < N ; i++){
        for(int j = 0; j < M ; j++){
            cin >> input_chess[i][j];
        }
    }
    
    
    for(int i = 0; i < N-7 ; i++){
        for(int j = 0; j < M-7 ; j++){
            int wcount = 0;
            int bcount = 0;
            for(int k = i; k < i+8 ; k++){
                for(int p = j; p < j+8 ; p++){
                    
                    // 화이트로 판이 시작할 때
                    if((k+p)%2 == 0&& input_chess[k][p] == 'B'){
                        wcount ++;
                    }else if((k+p)%2 == 1 && input_chess[k][p] == 'W'){
                        wcount ++;
                    }

                    // 블랙으로 판이 시작할 때
                    if((k+p)%2 == 0 && input_chess[k][p] == 'W'){
                        bcount ++;
                    }else if((k+p)%2 == 1 && input_chess[k][p] == 'B'){
                        bcount ++;
                    }
                }
            }
            if( min_color_change > wcount){
                min_color_change = wcount;
            }
            if( min_color_change > bcount){
                min_color_change = bcount;
            }
        }
    }
   
    cout << min_color_change << "\n";
    
    
    return 0;
}

성공한 사진!    

  MEMO 

: 내가 멍청한 걸까..? 문제를 한번 읽었을 때는 내용이 이해가 안 갔다..