1018번

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

1018번: 체스판 다시 칠하기

이 문제는 25682번과 완전 같은 코드이다.

먼저 N,M을 입력 받고, chess판을 채우기위한 값들을 입력받고, 그 다음에 시작지점이 검은색일때와 흰색일 때로 나누어서 생각한다.

그렇게 시작점과 같은색인 부분, 시작지점과 다른색인 부분을 (i+j)%2==0의 조건으로 판별해서 누적합을 계산한다. 물론 이 문제에서는 브루트포스법을 사용하라는 의도로 내었다. 브루트 포스로 한다면, 위의 조건으로 모든 부분의 값을 지정하고 범위마다 확인해야 할 것이다.

그치만 나는 시간을 단축하는 누적합을 사용하였다.

코드는 아래와 같다.

package backjoon.b1018;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b1018 {
    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());
        char[][] chess = new char[N][M];
        for(int i=0; i<N;i++){
            String tmp = br.readLine();
            for(int j=0; j<M; j++){
                chess[i][j]=tmp.charAt(j);
            }
        }
        System.out.println(Math.min(checkMin('B',chess,N,M),checkMin('W',chess,N,M)));
    }
    public static int checkMin(char color, char[][] chess, int N, int M){
        int[][] check=new int[N+1][M+1];
        int value;
        int comp = Integer.MAX_VALUE;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if((i+j)%2==0){
                    value = chess[i][j]!=color?1:0;
                }//시작지점과 같은 색
                else {
                    value = chess[i][j]==color?1:0;
                }//시작지점과 다른 색
                check[i+1][j+1]=check[i][j+1]+check[i+1][j]-check[i][j]+value;
            }
        }
        for(int i=1; i<=N-8+1; i++){
            for(int j=1; j<=M-8+1; j++){
                comp=Math.min(comp,check[i+7][j+7]-check[i-1][j+7]-check[i+7][j-1]+check[i-1][j-1]);
            }
        }
        return comp;
    }

}

맨 아래부분에 반복문으로 8x8체스판 자르기를 했는데 여기서 누적합을 사용하였기 때문에 (i+8-1, j+8-1)지점까지의 누적합은 (0,0)부터의 누적합이여서, 8x8에 포함되지 않는 부분의 누적합을 빼주는 방식으로 했다.

	i-1,j-1			i+3-1, j-1
	i-1, j+3-1			i+3-1,j+3-1

예를 들어 3x3짜리를 구한다고 했을 때, 누적합 계산을 위해서는 위의 표에 표시한 부분들을 이용해서 계산해야한다.

따라서 누적 값은 (i+3-1, j+3-1)-(i-1, j+3-1)-(i+3-1, j-1)+(i-1, j-1)이다. 여기서 (i-1, j-1)값을 더해주는 이유는 다른 값들에 이미 포함되어있어서 2번 빼었기 때문에 다시 한번 더해주는 것이다.

 

잘 이해가 되지 않는다면, 아래의 글도 읽어보고 아래의 문제도 풀어보자

https://parkjunbackend.tistory.com/32

b25682번