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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25682번 문제인 체스판 다시 칠하기 2이다.
문제는 아래 링크를 확인하자.

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

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

psum[r][c]를 (1행 1열을 좌상단, r행 c열을 우하단으로 하는 직사각형모양 판)을 좌상단 칸을 검은 색으로 하는 체스판 형태로 채색할 때 새로 칠해야 하는 칸의 수로 정의하자. 이 값은 psum[r-1][c] + psum[r][c-1] - psum[r-1][c-1]에 r행 c열의 칸을 새로 칠해야한다면 1, 아니면 0을 더해 값을 구해낼 수 있다. 위 식이 잘 이해되지 않는다면 간단한 그림을 그려 위 세 영역을 직사각형으로 나타내보자.

 

이 때, rr행 cc열을 우하단 칸으로 갖는 K행 K열 정사각형모양 판을 좌상단을 검은 색으로 하는 체스판 형태로 채색할 때 새로 칠해야하는 칸의 수는 psum[rr][cc] - psum[rr-K][cc] - psum[rr][cc-K] + psum[rr-K][cc-K]로 계산할 수 있다. 이 또한 앞선 식과 같이 간단한 그림을 그려 위의 각 값이 나타내는 영역을 표시해보면 직관적으로 이해할 수 있을 것이다.

 

이 문제에서의 체스판은 1행 1열의 칸이 흰색으로 칠해져 있어도 무방하다. 그러므로 1행 1열의 칸을 흰색으로 칠한다고 생각하고 위의 과정을 한번 더 반복하는 것으로 문제를 해결하자.

 

조금 더 관찰을 한다면 위의 두번째 과정에서 얻게 되는 배열은 먼젓번에서 얻은 배열을 이용해 얻을 수 있음을 알 수 있을 것이다. 구체적으로, 두번째 과정에서 얻게 되는 r행 c열 사각형의 값은 첫번째 과정에서 얻은 psum[r][c]를 이용해 r*c-psum[r][c]와 같이 계산할 수 있음을 확인하자.

 

이를 이용하면 psum 배열을 두번 구하지 않고도 아래와 같이 문제를 해결할 수 있다. 자세한 구현은 코드를 참고하자.

 

아래는 제출한 소스코드이다.

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

int R, C, K, KK;
string s[2000];
int psum[2001][2001];
int ans = 1000000007;

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

	cin >> R >> C >> K;
	KK = K * K;
	for (int r = 0; r < R; r++) cin >> s[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if ((r + c) & 1) {
				if (s[r][c] == 'B') psum[r + 1][c + 1] = 1;
			}
			else {
				if (s[r][c] == 'W') psum[r + 1][c + 1] = 1;
			}
			psum[r + 1][c + 1] += psum[r][c + 1] + psum[r + 1][c] - psum[r][c];
		}
	}

	for (int r = K; r <= R; r++) {
		for (int c = K; c <= C; c++) {
			int val = psum[r][c] - psum[r - K][c] - psum[r][c - K] + psum[r - K][c - K];
			ans = min(ans, min(val, KK - val));
		}
	}

	cout << ans;
}