25682번

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

25682번: 체스판 다시 칠하기 2

이 문제는 생각해내는 것 조차 어려웠다.

일단 체스판의 테이블을 만들고 누적합을 구해야한다는 생각은 했지만, 어떤 것의 누적합을 구해야 할지 몰랐다.

그래서 처음에는 테이블 자체의 누적합을 이용해서 해야하는건지 고민하느라 오래걸렸고, 그러다가 다른 사람들이 질문게시판에 올린 글을 보고, 틀린것을 누적합으로 계산하는 것이 맞겠다는걸 알았다. 그래서 이 문제를 틀린 것에 대한 누적합을 구하는 방법으로 생각했다.

 

풀이에서 경우의 수는 2가지이다. 문제에서 주어졌듯이 시작 지점이 흰색인지, 검은색인지 2가지다.

시작 지점을 검은색으로 한다면, 인덱스 값인 i,j의 합을 나눈 나머지가 0인 지점들은 모두 검은색이어야 한다.

그리고 그 외의 다른 지점들은 모두 흰색이어야한다.

즉, 따지고 보면 (i+j)%2==0인 지점들은 모두 시작지점과 같은 색이고, 그렇지 않은 부분들은 모두 시작지점과 다른 색인것이다.

검	흰	검	흰
흰	검	흰	검
검	흰	검	흰
흰	검	흰	검

4x4테이블일 경우 위와 같다.

그럼 이에 대해 주어진 테이블이 위와 다른 경우 고쳐야할 색으로 생각하여 값을 +1해주는 방식이 필요하다.

정리하자면, int형을 저장하는 check테이블에 check[i][j]=check[i][j-1]+check[i-1][j]-check[i-1][j-1]+(틀린경우=1)이와 같은 점화식이 나온다.

즉 이렇게 해서 고쳐야할 부분에 대한 누적합 테이블을 만들고, 이에 대해서 K구간만큼에 대한 누접합을 계산해내면 된다.

i<=k<=N,j<=K<=M이기 때문에 K로 만들 수 있는 구간은 0부터 N-K+1, M-K+1이다. 즉, i,j가 될 수 있는 구간이 1<=i<=N-K+1,1<=j<=M-K+1이다.

따라서 이 구간의 값을 구해서 그 중 최솟값을 구하면된다.

만약 4 4 3의 입력이 들어오면 K로 만든 구간의 값은

check[1+3-1][1+3-1]-check[1-1][1+3-1]-check[1+3-1][1-1]+check[1-1][1-1]

=check[3][3]-check[0][3]-check[3][0]+check[0][0]이다.

틀린경우 = check[i][j]-check[i][j-1]-check[i-1][j]+check[i-1][j-1]로 위의 처음 check테이블을 구한 점화식을 변형하면 얻을 수 있다.

다르게 말하면, i=K,j=K라고하여 check[i][j]-check[i][j-K]-check[i-K][j]+check[i-K][j-K]로 할 수 있다.

그래서 정답코드는 입력받은 테이블을 0부터 시작할 때와 1부터 시작할 때 둘로 나누었다.

package backjoon.b25682;

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

public class b25682 {
    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());//row
        int M = Integer.parseInt(st.nextToken());//column
        int K = Integer.parseInt(st.nextToken());
        char[][] chess = new char[N+1][M+1];
        String row;
        for(int i=0;i<N; i++){
               row = br.readLine();
               for(int j=0; j<M; j++){
                   chess[i][j]=row.charAt(j);
               }
           }//1 1부터 시작하는 테이블 완성
        System.out.println(Math.min(checkMin('B',N,M,K,chess),checkMin('W',N,M,K,chess)));
    }
    static int checkMin(char color,int N, int M, int K, char[][] chess){
        int count = Integer.MAX_VALUE;
        int value;
        int[][] check= new int[N+1][M+1];
        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;
                }//시작지점과 같은색이면 0, 다른색이면 1 시작지점과 같은색인 지점들
                else {
                    value = chess[i][j]==color?1:0;
                }//시작지점과 다른색이면 0, 같은색이면 1 시작지점과 다른색인 지점들
                check[i+1][j+1]=check[i][j+1]+check[i+1][j]-check[i][j]+value;
            }
        }
        for(int i=1; i<=N-K+1;i++){
            for(int j=1; j<=M-K+1; j++){
                count=Math.min(count,check[i+K-1][j+K-1]-check[i+K-1][j-1]-check[i-1][j+K-1]+check[i-1][j-1]);
            }
        }
        return count;
    }
}

package backjoon.b25682;

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

public class b25682_2 {
    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());//row
        int M = Integer.parseInt(st.nextToken());//column
        int K = Integer.parseInt(st.nextToken());
        char[][] chess = new char[N+1][M+1];
        String row;
        for(int i=1;i<=N; i++){
            row = br.readLine();
            for(int j=1; j<=M; j++){
                chess[i][j]=row.charAt(j-1);
            }
        }//1 1부터 시작하는 테이블 완성
        System.out.println(Math.min(checkMin2('B',N,M,K,chess),checkMin2('W',N,M,K,chess)));

    }
    static int checkMin2(char color,int N, int M, int K, char[][] chess){
        int count = Integer.MAX_VALUE;
        int value;
        int[][] check= new int[N+1][M+1];
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                if((i+j)%2==0){
                    value = chess[i][j]!=color?1:0;
                }//시작지점과 같은색이면 0, 다른색이면 1 시작지점과 같은색인 지점들
                else {
                    value = chess[i][j]!=color?0:1;
                }//시작지점과 다른색이면 0, 같은색이면 1 시작지점과 다른색인 지점들
                check[i][j]=check[i][j-1]+check[i-1][j]-check[i-1][j-1]+value;
            }
        }
//        for(int i=1; i<=N-K+1;i++){
//            for(int j=1; j<=M-K+1; j++){
//                count=Math.min(count,check[i+K-1][j+K-1]-check[i+K-1][j-1]-check[i-1][j+K-1]+check[i-1][j-1]);
//            }
//        }
        for(int i=K; i<=N;i++){
            for(int j=K; j<=M; j++){
                count=Math.min(count,check[i][j]-check[i-K][j]-check[i][j-K]+check[i-K][j-K]);
            }
        }

        return count;

    }
}