boj 25682 체스판 다시 칠하기 2

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

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

2차원 배열 내 누적합 문제입니다.

2차원 누적합은 (sx, sy) ~ (ex, ey)의 누적합을 말하며, dp[i][j] = cur + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] 공식을 활용해야 합니다.

 

체스판은 검은색, 흰색이 번갈아 칠해져있어야 하고, (1, 1) 지점의 색은 정해지지 않았습니다.

따라서 (1, 1) 지점에 검은색이 올 경우와 흰색이 올 경우를 모두 구해서 최솟값을 구해야 합니다.

이를 위해 dp를 두개 사용합니다.

 

좌표의 x, y값을 더한 값이 홀수인 좌표들끼리와 짝수인 좌표들끼리의 색은 같습니다.

이를 활용하여 해당 좌표에 색이 바껴야하는지에 대해서 각각 누적합을 구할 수 있습니다.

dp를 채웠다면 K * K 크기의 정사각형의 누적합들을 순회하며 최솟값을 구하도록 합니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 2001
using namespace std;
 
char list[MAX][MAX];
int bdp[MAX][MAX], wdp[MAX][MAX];
int N, M, K;
 
void getPrefixSum() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            bdp[i][j] = bdp[i - 1][j] + bdp[i][j - 1] - bdp[i - 1][j - 1];
            wdp[i][j] = wdp[i - 1][j] + wdp[i][j - 1] - wdp[i - 1][j - 1];
 
            if (list[i][j] == 'W') {
                if ((i + j) % 2) {
                    wdp[i][j]++;
                }
                else {
                    bdp[i][j]++;
                }
            }
            else {
                if ((i + j) % 2) {
                    bdp[i][j]++;
                }
                else {
                    wdp[i][j]++;
                }
            }
        }
    }
}
 
void func() {
    getPrefixSum();
    int ret = 2147483647;
    for (int i = K; i <= N; i++) {
        for (int j = K; j <= M; j++) {
            ret = min(ret, bdp[i][j] - bdp[i - K][j] - bdp[i][j - K] + bdp[i - K][j - K]);
            ret = min(ret, wdp[i][j] - wdp[i - K][j] - wdp[i][j - K] + wdp[i - K][j - K]);
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}