[BOJ 25682] 체스판 다시 칠하기

생각보다 조금 귀찮은 문제다.

일단 기본적인 아이디어는, 누적 합 배열을 이용하는 것이다.

가장 왼쪽 위 칸이 흰색일 때(WBWB...)와 검은색일 때(BWBW...)로 구분하여

새로 칠해야 할 칸의 수를 2차원 누적 합 배열로 미리 저장해둔다.

그리고 일일이 가능한 모든 경우를 검토하면서 정답을 구한다.

 

#include <stdio.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int n, m, k;
int w[2001][2001], b[2001][2001];

int main(void) {
	scanf("%d %d %d", &n, &m, &k);
	getchar();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c; scanf("%c", &c);
			if (!((i + j) & 1)) {
				if (c == 'B') {
					w[i][j] = 1;
					b[i][j] = 0;
				} else {
					w[i][j] = 0;
					b[i][j] = 1;
				}
			} else {
				if (c == 'B') {
					w[i][j] = 0;
					b[i][j] = 1;
				} else {
					w[i][j] = 1;
					b[i][j] = 0;
				}
			}
			w[i][j] += w[i - 1][j] + w[i][j - 1] - w[i - 1][j - 1];
			b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
		}
		getchar();
	}
	int mn = 1e9;
	for (int r1 = 1; r1 <= n - k + 1; r1++) {
		for (int c1 = 1; c1 <= m - k + 1; c1++) {
			int r2 = r1 + k - 1, c2 = c1 + k - 1;
			mn = MIN(mn, w[r2][c2] - w[r1 - 1][c2] - w[r2][c1 - 1] + w[r1 - 1][c1 - 1]);
			mn = MIN(mn, b[r2][c2] - b[r1 - 1][c2] - b[r2][c1 - 1] + b[r1 - 1][c1 - 1]);
		}
	}
	printf("%d", mn);
	return 0;
}

 

 

홀짝 구분해가면서 2차원 누적 합 배열 만드는게 좀 귀찮은 과정이다.

대체 어디서 체스판도 아닌데 흰색 검은색이 번갈아 칠해져있는 저딴 이상한 보드를 구한거야~~!!!