누적합 문제.
유난히 어려워하는 문제가 있다. 특히 수학 관련 문제. 풀이식을 설계해야하는 그리디, DP, 누적합 등이 그렇다.
이번 문제도 풀다 풀다 지쳐서, 결국 답을 확인했던 문제. 답을 보았는데도 잘 이해가 안가서 시간이 오래걸렸다.
해당 문제에서는 총 두 개의 점화식이 필요하다.
먼저 보드의 시작이 하양, 검정으로 정해져 있지 않다. 따라서, 검정으로 시작하여 색칠을 다시하는 경우와, 하양으로 시작하여 색칠을 다시하는 경우를 파악해야한다. 두가지 경우를 모두 판단하여 그 가운데 가장 작은 값이 답이 될 것이다.
먼저 색칠이 필요한 곳을 판단하는 식은 다음과 같다.
점화식 = 위 행에서 누적한 총 가짓 수 + 이번행의 직전까지 누적한 가짓 수 - 중복 값
이후 전체 누적합에서 K 범위에서 나타나는 가짓수를 나타내는 점화식은 다음과 같다.
점화식 = K 범위 만큼 총 누적한 가짓 수 - 행+K 만큼의 총 누적한 가짓 수 - 열+K 만큼의 총 누적한 가짓 수 + 중복 값
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static char[][] board;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new char[N][M];
char[] temp;
for (int i = 0; i < N; i++) {
temp = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
board[i][j] = temp[j];
}
}
int[][] prefixSumB = prefixSum('B');
int[][] prefixSumW = prefixSum('W');
System.out.println(Math.min(calculate(prefixSumB), calculate(prefixSumW)));
}
private static int calculate(int[][] prefixSum) {
int cnt = (int) 1e9;
for (int i = 1; i <= N - K + 1; i++) {
for (int j = 1; j <= M - K + 1; j++) {
int num = prefixSum[i + K - 1][j + K - 1] - prefixSum[i + K - 1][j - 1] - prefixSum[i - 1][j + K - 1] + prefixSum[i - 1][j - 1];
cnt = Math.min(cnt, num);
}
}
return cnt;
}
private static int[][] prefixSum(char st) {
int[][] temp = new int[N + 1][M + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int curr = ((i + j) % 2 == 0) ? board[i][j] == st ? 0 : 1 : board[i][j] == st ? 1 : 0;
temp[i + 1][j + 1] = temp[i + 1][j] + temp[i][j + 1] - temp[i][j] + curr;
}
}
return temp;
}
}