[C++] 25682: 체스판 다시 칠하기 2

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

제한

1 ≤ N, M ≤ 2000
1 ≤ K ≤ min(N, M)

풀이

2차원 누적합을 이용한 베리하드 문제 ㅜ

input을 한 칸씩 받으면서, 2차원 누적합 배열을 만든다.
좌표 (1, 1)부터 input을 받고, 첫번째 칸에 검정을 칠하는 것을 기준으로 배열을 만들었다.
해당 칸의 누적값은 위 기준으로 체스판을 만들기 위해 칠해야 하는 횟수이다.

(i, j)에 input을 받을 때,
i + j가 짝수라면 검정이 와야 한다. 검정이 아닌 하양이 들어온다면, 다시 검정으로 칠해야 하므로, 해당 좌표의 값을 1로 두고 누적합을 구한다. (검정이 들어온다면 0)
i + j가 홀수라면 하양이 와야 한다. 하양이 아닌 검정이 들어온다면, 다시 하양으로 칠해야 하므로, 해당 좌표의 값을 1로 두고 누적합을 구한다. (하양이 들어온다면 0)

보드에서 만들 수 있는 모든 k x k를 검사하여 최솟값을 구한다.
k x k에서 가장 오른쪽 아래의 좌표를 (i, j)라 할 때, k x k를 체스판 모양으로 칠하기 위한 개수는 2차원 누적합 공식에 의해
count_painting = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k]
이다.

현재 검사하는 2차원 누적합 배열은 보드의 첫번째 좌표를 검정으로 하는 체스판을 기준으로 만들었다. 따라서
k * k - count_painting은 보드의 첫번째 좌표를 하양으로 하는 체스판을 기준으로 칠하는 횟수가 된다.
둘 중 더 작은 수를 구한 후, 그 값이 total_min보다 작다면 total_min을 갱신한다.

코드

#include <iostream>

using namespace std;

void input_data(void);
void find_min(void);

int n, m, k, total_min = 2000001;
int prefix_sum[2001][2001];

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

	input_data();
	find_min();
	cout << total_min << '\n';

	return (0);
}

void input_data(void)
{
	cin >> n >> m >> k;

	int i = 0;
	while (++i <= n)
	{
		int j = 0;
		while (++j <= m)
		{
			char color;
			cin >> color;
			if (((i + j) % 2 == 0 && color != 'B') || ((i + j) % 2 != 0 && color == 'B'))
				prefix_sum[i][j] = 1;
			prefix_sum[i][j] += prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1];
		}
	}

	return ;
}

void find_min(void)
{
	int i, j;

	i = k - 1;
	while (++i <= n)
	{
		j = k - 1;
		while (++j <= m)
		{
			int count_painting = prefix_sum[i][j] - prefix_sum[i - k][j] - prefix_sum[i][j - k] + prefix_sum[i - k][j - k];
			count_painting = min(k * k - count_painting, count_painting);
			total_min = min(total_min, count_painting);
		}
	}

	return ;
}

성공 !