[c++] 백준 25682, 체스판 다시 칠하기 2

백준 25682

알고리즘 분류 : prefix sum (누적 합)

🌲 문제 요약

입력받은 임의의 MxN 크기의 보드를 KxK 크기의 보드로 잘라낸 뒤 색칠을 통해 하나의 체스판으로 만들려 한다. 이때 다시 칠해야 하는 정사각형의 최소 개수는 몇 개일까?

🌲 문제 풀이

2차원에서의 누적 합을 이용하여 문제를 해결하였다.

chess 함수를 통해, 입력받은 배열 board와 두 개의 체스판(첫 번째 칸이 검은색인 체스판, 첫 번째 칸이 흰색인 체스판)을 각각 비교한 뒤, 더 작은 값을 정답으로 출력했다.

chess 함수에서는 board와 체스판을 비교하여, 만약 색칠이 필요하다면 변수 value에 1, 색칠이 필요 없다면 value에 0을 저장하고 이를 토대로 누적 합 배열 pSum을 완성시켰다.

다음으로 pSum 안에서 반복문을 통해 KxK 크기의 보드를 차례로 살펴보며 색칠이 필요한 정사각형의 최소 개수를 구했다.

🌲 주의

board의 색깔과 인자로 불러온 변수 color를 비교하는 과정은 조건문을 통해 해결했다.
이때 (i+j) % 2 == 0인 경우는 인자로 불러온 color 그대로, (i + j) % 2 == 1인 경우는 인자로 불러온 color 반대로 생각해야 함에 유의하자.

🌲 코드

#include <iostream>
#include <algorithm>

using namespace std;
int N, M, K;
char board[2000][2000];

int chess(char color) {
	int value, pSum[N + 1][M + 1] = {};
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!((i + j) % 2)) value = board[i][j] != color; // (i + j) % 2 = 0인 경우, 인자로 불러온 color 그대로
			else value = board[i][j] == color; // (i + j) % 2 = 1인 경우, 인자로 불러온 color 반대로
			
			pSum[i + 1][j + 1] = pSum[i][j + 1] + pSum[i + 1][j] - pSum[i][j] + value;
		}
	}
	int tmp, result = 100000000;
	
	for (int i = 0; i <= N - K; i++) {
		for (int j = 0; j <= M - K; j++) {
			tmp = pSum[i + K][j + K] - pSum[i][j + K] - pSum[i + K][j] + pSum[i][j];
			result = (tmp < result) ? tmp : result;
		}
	}
	
	return result;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}
	
	cout << min(chess('B'), chess('W')) << '\n';
}