BOJ 25682 C++

문제접근

(1,1)이 검은색인것을 기준으로 다시 칠해야하는 수를 저장하는 2차원 배열을 만듭니다.

k * k - (1,1)이 검은색인 것 기준 다시 칠해야하는 수

이렇게 하면 지금 검사하는 좌표(k + i)(k + j)에서의 반대색 즉 반전한 것에서 다시 칠해야 하는 수를 찾을 수 있겠네요.
둘이 비교만 하면 찾을 수 있습니다.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

int n, m, k;
int board[2001][2001];  // 보드를 나타내는 2차원 배열

// 보드의 각 셀 값을 설정하는 함수
void setting(int i, int j, char c)
{
    // 만약 행 인덱스와 열 인덱스의 합이 짝수이고 문자가 'B'가 아니거나,
    // 행 인덱스와 열 인덱스의 합이 홀수이고 문자가 'B'라면, 셀 값을 1로 설정
    if (((i + j) % 2 == 0 && c != 'B') || ((i + j) % 2 != 0 && c == 'B'))
    {
        board[i][j] = 1;
    }
    // 주변 셀의 값에 기반하여 셀 값을 업데이트
    board[i][j] += board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1];
}

// 필요한 최소한의 페인트 수를 계산하는 함수
int sol()
{
    int ans = 4000001;
    for (int i = k; i <= n; i++)
    {
        for (int j = k; j <= m; j++)
        {
            int paint = board[i][j] - board[i - k][j] - board[i][j - k] + board[i - k][j - k];
            int rPaint = k * k - paint;
            ans = min(ans, min(paint, rPaint));
        }
    }
    return ans;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            setting(i, j, c);
        }
    }
    cout << sol();

    return 0;
}