[BOJ/C++] 25682 - 체스판 다시 칠하기 2

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

25682번: 체스판 다시 칠하기 2

---

백준 단계별 밀다가 찾은 괜찮은 문제.

누적합이란걸 몰랐다면 시간이 더욱 오래걸렸을 듯?

 

"체스판을 자르고 색칠하기"가 아니라, "색칠을 먼저 하고, 자르기"로 생각해보면,

색칠한 칸들에 대해서 2차원 누적합 배열을 구할 수 있다. 

"어떤값에 대해서 누적합 배열을 만들 것인가"를 잘 생각하면 구현은 간단했다.

 

 

"체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다."

 

두 경우에 대해서 올바르게 색칠된 체스판을 만들고, 입력과 비교하여 같은부분은 0, 다른부분(즉, 색칠해야하는 부분)은 1을 저장한다.

이후 2차원 누적합 배열로 만들어 준 후, 자를 수 있는 모든 가짓수에 대해 필요한 색칠 수를 구해주면 된다.

 

 

 

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/


string board[2001],type[2001];
int s[2001][2001];
int n,m,k;
int sol(int t){
    rep(i,0,n){
        rep(j,0,m){
            s[i+1][j+1] = (board[i][j]!="WB"[(i+j+t)%2]) + s[i+1][j];
        }
    }
    rep(i,0,n){
        rep(j,0,m){
            s[i+1][j+1] += s[i][j+1];
        }
    }
    int ret=2e9;
    rep(i,1,n-k+2){
        rep(j,1,m-k+2){
            pii st = {i,j};
            pii en = {i+k-1,j+k-1};
            int tmp = s[en.X][en.Y] - s[en.X][st.Y-1] - s[st.X-1][en.Y] + s[st.X-1][st.Y-1];
            ret = min(ret,tmp);
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k;
    rep(i,0,n) cin>>board[i];
    cout<<min(sol(0),sol(1))<<'\n';
}