문제

풀이과정

누적합 문제.
유난히 어려워하는 문제가 있다. 특히 수학 관련 문제. 풀이식을 설계해야하는 그리디, 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;
    }
}