BOJ 1018 : 체스판 다시 칠하기 - C++

13141 단어 bojboj

체스판 다시 칠하기

코드

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    char origin[N][M];
    for(int i=0;i<N;i++)
        cin >> origin[i];

    int MIN=N*M;
    for(int a=0;a<=N-8;a++)
    {
        for(int b=0;b<=M-8;b++)
        {
            int ans[2] = {0,0};
            char board[2][8][8];
            for(int i=0;i<8;i++)
                for(int j=0;j<8;j++)
                {
                    board[0][i][j] = origin[i+a][j+b];
                    board[1][i][j] = origin[i+a][j+b];
                }
            for(int z=0;z<2;z++)
            {
                char prev;
                if(z == 0) prev='B';
                else prev='W';
                for(int i=0;i<8;i++)
                {
                    if(i != 0) prev=board[z][i-1][0];
                    for(int j=0;j<8;j++)
                    {
                        if(board[z][i][j] == prev){
                            ans[z]++;
                            if(prev == 'W') board[z][i][j] = 'B';
                            else board[z][i][j] = 'W';
                        }
                        if(prev == 'W') prev = 'B';  
                        else prev = 'W';
                    }
                }
            }
            MIN = min(MIN, min(ans[0], ans[1]));
        }
    }
    cout << MIN;
    return 0;
}
  • 로직
    1) 전체 체스판을 origin[][]에 저장
    2) 전체 for문 틀로 a=N-8 ~ b=M-8까지 돌며, board[][]에 정해진 범위까지를 복사!
    3) 8x8 체스판인 board[][]에서 맨 왼쪽 위가 'W' 경우 / 'B'경우 가정해서 최소 변경회수 찾기
    4) min값 갱신
  • 하라는대로 구현만 하면 풀리는 문제

좋은 웹페이지 즐겨찾기