[백준] 25682: 체스판 다시 칠하기 2 - JAVA

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

 

풀이

M x N 사이즈의 보드가 주어지고, K x K 의 크기로 잘라 이 구역을 체스판 모양으로 만들어야한다. 뭔가 이 말을 이해하는데 오래걸렸다...

체스판은 흰색 검은색이 번갈아 나온다.

체스판의 첫 칸을 (0, 0)이라고 한다면, 첫칸이 흰색이면 격자의 행 + 격자의 열 번호를 더했을 때 짝수이면 흰색, 홀수이면 검은색이다.

첫칸이 검은색이면 마찬가지 방식으로 반대로 된다.

BW로 이루어진 보드를 입력받으면서 위의 규칙에 맞게 첫칸이 흰색인 배열, 첫칸이 검은색인 배열에 각각 넣었다.

이 배열에서 1이 의미하는 것은 격자의 색깔이 맞지 않아 새로 칠해야 한다는 의미이다.

잘 맞게 칠해져있는 것은 0으로 한다.

검은색, 흰색 각각 2차원 누적합 배열을 만들어주고,

K x K 크기에 맞게 잘라가면서 해당 구역에 몇 개를 새로 칠해야 하는지 구해주면 된다.

int cnt = sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] + sum[i - 1][j - 1];

sum 이차원배열에서 K x K 크기의 구역에 새로 칠해야 할 개수를 구하는 방법은 위와 같다.

 

---

 

메모리: 87060KB
시간: 500ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] white = new int[n][m];
        int[][] black = new int[n][m];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                char color = line.charAt(j);
                if ((i + j) % 2 == 0) {
                    white[i][j] = color == 'W' ? 0 : 1;
                    black[i][j] = color == 'B' ? 0 : 1;
                } else {
                    white[i][j] = color == 'W' ? 1 : 0;
                    black[i][j] = color == 'B' ? 1 : 0;
                }
            }
        }

        int[][] sumWhite = new int[n + 1][m + 1];
        int[][] sumBlack = new int[n + 1][m + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                sumWhite[i][j] = sumWhite[i - 1][j] + sumWhite[i][j - 1] - sumWhite[i - 1][j - 1] + white[i - 1][j - 1];
                sumBlack[i][j] = sumBlack[i - 1][j] + sumBlack[i][j - 1] - sumBlack[i - 1][j - 1] + black[i - 1][j - 1];
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                int cntWhite = sumWhite[i + k - 1][j + k - 1] - sumWhite[i - 1][j + k - 1] - sumWhite[i + k - 1][j - 1]
                        + sumWhite[i - 1][j - 1];
                int cntBlack = sumBlack[i + k - 1][j + k - 1] - sumBlack[i - 1][j + k - 1] - sumBlack[i + k - 1][j - 1]
                        + sumBlack[i - 1][j - 1];
                answer = Math.min(answer, Math.min(cntWhite, cntBlack));
            }
        }

        System.out.println(answer);
    }

}