(25682) 체스판 다시 칠하기 2

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

단계별로 풀어보기

22단계(누적 합) 6번째

 

 

 

체스판과 같은 크기의 벡터를 생성하고, 체스판을 임의의 제대로 색칠된 체스판과 비교하여 색이 맞으면 0, 틀리면 1로 둔다.

이제 구간 ((i-k,j-k),(i,j))의 합은 이 구간으로 잘랐을 때 다시 칠해야 하는 칸의 수와 같다. 구간합은 누적합 배열을 사용해 빠르게 구할 수 있다.

이때 우리가 임의로 설정한 체스판의 색반전 버전도 제대로 색칠된 체스판이므로, 전체 칸 수에서 계산한 값을 뺀 결과도 다시 칠해야 하는 칸의 수가 될 수 있다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, k;
  
  cin >> n >> m >> k;
  
  vector s(n+1, vector<int> (m+1));
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      char c;
      
      cin >> c;
      
      s[i][j]= ((i+j)&1 ? c=='B' : c=='W');
      s[i][j]+= s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    }
  }
  
  int ans= k*k;
  
  for(int i=k;i<=n;i++){
    for(int j=k;j<=m;j++){
      int t= s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k];
      
      ans= min(ans, t);
      ans= min(ans, k*k-t);
    }
  }
  
  cout << ans;
  
  return 0;
}