백준 재활치료 (5) 25682 체스판 다시 칠하기 2

일단 간단히 보이는대로만 풀면 4중 for문이 나온다, 아무리 생각해도 그건 아닌거 같고 살펴보니 이 문제는 누적합 개념을 활용해야 하는 문제라고 한다

누적합이란?

보통 어떤 배열의 구간합을 구할 때 i ~ j 까지 원소를 하나씩 더하는 개념으로 작용한다, 그러나 이 구간합을 미리 더해놓는다면 더 간단해질 수 있다

Ex) A = [1 2 3 4 5] 배열이 있다고 치면 원래 A[1] ~ A[3] 를 더하고 싶으면
2 + 3 + 4 즉 3번을 돌려야 한다

그런데 미리 각 구역까지의 합을 미리 세팅해둔다고 하면

S[1 3 6 10 15] 이런 식으로 세팅해둘 수 있다

이렇게 됐을 때 위 식을 다시 해보면 S[4] - S[1], 즉 S[j] - S[i-1] 이런 식으로 한번만 구하면 되는 것이다

결국 구간합의 시간을 줄여줄 수 있는 로직인 것이다

결론 함수부터 보여주고 분석해보도록 하겠다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int N, M, K;
	cin >> N >> M >> K;

	vector<string> Chess(N);
	for(int i = 0; i < N; ++i) {
		cin >> Chess[i];
	}

	vector<vector<int>> B(N + 1, vector<int>(M + 1, 0));
	vector<vector<int>> W(N + 1, vector<int>(M + 1, 0));

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			char current = Chess[i - 1][j - 1];

			char expectB = ((i + j) % 2 == 0) ? 'B' : 'W';
			char expectW = ((i + j) % 2 == 0) ? 'W' : 'B';

			int diffB = (current != expectB);
			int diffW = (current != expectW);

			B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + diffB;
			W[i][j] = W[i - 1][j] + W[i][j - 1] - W[i - 1][j - 1] + diffW;
		}
	}

	int ans = 1e9;

	for (int i = 1; i <= N - K + 1; i++) {
		for (int j = 1; j <= M - K + 1; j++) {
			int r2 = i + K - 1;
			int c2 = j + K - 1;

			int repaintB = B[r2][c2] - B[i - 1][c2] - B[r2][j - 1] + B[i - 1][j - 1];
			int repaintW = W[r2][c2] - W[i - 1][c2] - W[r2][j - 1] + W[i - 1][j - 1];

			ans = min(ans, min(repaintB, repaintW));
		}
	}

	cout << ans << '\n';
}

vector<string> Chess(N);
	for(int i = 0; i < N; ++i) {
		cin >> Chess[i];
	}

한글자씩 넣지 말고 string화 해서 한줄씩 넣는 개념으로 다가가면 편하게 풀 수 있을 것이다

vector<vector<int>> B(N + 1, vector<int>(M + 1, 0));
vector<vector<int>> W(N + 1, vector<int>(M + 1, 0));

각각 시작점이 B인 경우, W인 경우를 가정해 완벽히 정상인 체스판을 만든다고 가정한다
이렇게 하고 틀린 부분과 비교해서 틀린것만 집어내는게 계산에 더 유리할 수 있기 때문에 적용해본다
+1씩 하는 이유는 한바퀴를 0으로 둘러서 계산에 용이하게 하려는 것이다

for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			char current = Chess[i - 1][j - 1];

			char expectB = ((i + j) % 2 == 0) ? 'B' : 'W';
			char expectW = ((i + j) % 2 == 0) ? 'W' : 'B';

			int diffB = (current != expectB);
			int diffW = (current != expectW);

			B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + diffB;
			W[i][j] = W[i - 1][j] + W[i][j - 1] - W[i - 1][j - 1] + diffW;
		}
	}

이제 한바퀴를 0으로 돌린 것을 제외하고 1 ~ N, 1 ~ M에 적용을 해보기 시작한다
char current은 0을 감싼걸 빼서 제외하고 쭉쭉 넣어보는 것이다

그리고 expectB, W은 원래 거기에 들어가야할 것들에 대해 적용해보는 것이다
앞이 B인 경우와 W인 경우를 둘 다 비교한다

그 아래에는 current와 방금 구한 expect와 다른지 구한다
c++에서는 bool문이 맞으면 1, 틀리면 0을 int로 뱉을 수 있기 때문에 뱉는다

이제 이 아래에 누적합 업데이트 공식을 구하는 것이다
앞이 B일 때 2차원 벡터의 누적합을 구하는 공식을 적용해본다
계속 누적합이 될 테니 B[i-1][j]는 왼쪽의 모든 줄을 더한 시점의 값이 될 것이다
마찬가지로 B[i][j-1]도 위쪽의 모든 줄을 더한 시점의 값이 될 것이다
그렇게 되면 간단히 숫자로 예시를 들어보자면

a a a b
a a a b
a a a b
a a a c = B[i-1][j]

a a a a
a a a a
a a a a
b b b c = B[i][j-1]

을 둘 다 더한다고 하면 진한 부분은 2번 더하니 B[i - 1][j - 1]을 빼야 하는 것이다
그 후 방금 diff을 더하면 깔끔히 2차원 벡터의 누적합을 구할 수 있다

	int ans = 1e9;

	for (int i = 1; i <= N - K + 1; i++) {
		for (int j = 1; j <= M - K + 1; j++) {
			int r2 = i + K - 1;
			int c2 = j + K - 1;

			int repaintB = B[r2][c2] - B[i - 1][c2] - B[r2][j - 1] + B[i - 1][j - 1];
			int repaintW = W[r2][c2] - W[i - 1][c2] - W[r2][j - 1] + W[i - 1][j - 1];

			ans = min(ans, min(repaintB, repaintW));
		}
	}

	cout << ans << '\n';
}

이제 ans는 최대값으로 잡고
2중 for문을 돌면서 N, M에서 판 크기만큼 빼고 돌리기 시작한다

r2, c2는 지금 어디까지 누적합을 더해야하는지 잡아주는 x, y축을 잡아준다
그리고 위에서 합을 더할 때 더하고 더하고 뺀 것과 마찬가지로 실제 값을 구하려면 빼고 빼고 2번 뺀 걸 더한다고 계산하면 조금 편하게 보일 것이다

이렇게 하고 ans와 B 기준, W 기준 중 작은걸 골라 또 min을 구하고, 이걸 돌리면 결론적으론 답을 알 수가 있다

어렵네요..