[G4] 백준 25682번 체스판 다시 칠하기 2 C++ 누적 합

리뷰

 

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

2차원 누적합 문제, 풀어보지 않은 유형이라 많이 고전했다.

 

 

전역 변수

• n, m : 맵의 세로/가로 크기를 저장할 변수
• k : 정사각형의 크기를 저장할 변수
• lst : 체스판의 정보를 입력 받을 문자열 배열

 

함수

1. chk

int chk(char col)

 

체스판에서 col로 시작하는 경우에 대해 다시 칠해야 하는 정사각형 개수의 최솟값을 찾는 함수

1. 매개 변수로 시작 지점의 색깔을 문자 변수 col로 입력 받는다.
2. 보드 정보를 값으로 변환하기 위한 2차원 벡터 vals를 n * m크기로 초기화 한다.
3. 누적합을 저장할 2차원 벡터 preSums는 n + 1 * m + 1크기로 초기화 한다.
4. vals배열은 i + j가 홀수인 칸에는 lst배열에서 값이 col과 같다면 1을 저장한다.
5. 반대로 i + j가 짝수인 칸에는 lst배열에서 값이 col과 다르다면 1을 저장한다.
6. preSums의 i + 1, j + 1인 칸에는 preSums의 좌측, 우측칸을 더하고, 왼쪽 위 대각선을 빼고 vals값을 더해준다.
7. 초기 ans값을 매우 큰 값으로 초기화 하고 최소값을 찾는 로직을 진행한다.
8. 0 ~ n - k, 0 ~ m - k좌표를 순회하며 preSums의 i + k, j + k의 값에서 i, j + k / i + k, j값을 빼고 i, j값을 더해준다.
9. ans와 비교하여 더 작은 값을 ans에 갱신해 나가며 탐색이 종료되면 ans에 저장된 값을 리턴해 준다.

 

문제풀이

1. n, m, k값을 입력 받고, n개의 문자열을 lst배열에 입력 받아준다.
2. chk함수에 'W'와 'B'를 각각 매개변수로 전달 후 받은 리턴값 중 작은 값을 출력해 준다.

 

트러블 슈팅

1. 초기에 행별로 누적합을 구해 문제를 풀이했으나 그 방식엔 개수만 저장되어 있어 제대로 된 답이 나오지 않았다.
2. 누적합을 사각형의 형태로 저장 후 제출하니 AC를 받았다, dp의 느낌이 나는 문제였다.

 

참고 사항

• 시작점이 'B'인 경우와 'W'인 경우를 각각 구해주어야 한다.

 

정답 코드

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

int n, m, k;
string lst[2000];

int chk(char col) {
	vector<vector<int>> vals(n, vector<int>(m, 0));
	vector<vector<int>> preSums(n + 1, vector<int>(m + 1, 0));

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if ((i + j) % 2) vals[i][j] = lst[i][j] == col;
			else vals[i][j] = lst[i][j] != col;
			preSums[i + 1][j + 1] = preSums[i][j + 1] + preSums[i + 1][j] - preSums[i][j] + vals[i][j];
		}
	}

	int ans = 2e9;
	for (int i = 0; i <= n - k; ++i) {
		for (int j = 0; j <= m - k; ++j) {
			ans = min(ans, preSums[i + k][j + k] - preSums[i][j + k] - preSums[i + k][j] + preSums[i][j]);
		}
	}
	return ans;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];

	cout << min(chk('W'), chk('B'));
}