백준 25682번 : 체스판 다시 칠하기 2[C#]

단계별로 문제를 풀면 체스판 다시 칠하기 1은 브루트포스로 풀었는데요. 달라진건 보드판의 크기가 커지고, 시간제한도 줄었다는 점입니다.

 

누적합 문제를 풀다보면 누적합의 도착점 인덱스의 값에서 시작점 인덱스의 값을 빼면서 빠르게 값을 찾는 패턴이 자주 등장했습니다. 이 문제에도 같은 방식으로 접근하여 row를 기준으로 1차원 누적합을 구했는데 시간초과가 났습니다.

 

1. 이 문제는 2차원 누적합으로 접근해야합니다. 특정 좌표 x,y에서의 누적합은 0,0부터 x,y를 완전한 보드판으로 만들 때 몇 번 칠해야하는지의 횟수입니다.

> 2차원 좌표 (x,y)의 누적합을 초기화 하는 방법은 sum(x,y) = ( 해당 인덱스에서 추가 할 값 ) - ( 그 외 영역의 값의 합) = ( 해당 인덱스에서 추가할 값) + sum(x-1,y) + sum(x,y-1) - (x-1,y-1) 입니다. 필요한 값을 이전에 구해놓은 sum에서 찾아서 넣고, 겹치는 부분은 빼는 방식이죠.

* 팁이라면 인덱스를 0이 아닌 1부터 시작하면 -1을 계산할 때 편리합니다.

*  K*K - B로 시작할 때의 칠하는 횟수  = W로 시작할 때의 칠하는 횟수입니다. 둘 줄 하나만 구하면 되요.

 

2. 모든 좌표에 대해 위의 식으로 누적합을 구했다면 필요한 영역의 횟수를 구하는 방법도 접근 방식이 동일합니다.

(row, col)부터 (row+K , col+K) 영역의 횟수를 구하는 방법은

 

(row+K,col+K)의 누적합에서 사용하지 않는 영역을 빼는 것이지요.

 

3. 모든 좌표를 기준으로 K*K 크기의 영역에서 횟수를 구하고, 가장 작은 값을 출력합니다.

* B로 시작, W로 시작하는 경우를 모두 체크해야합니다.

 

using System.Text;

class Program
{

    static void Main()
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        string[] line = sr.ReadLine().Split();

        int N = int.Parse(line[0]);
        int M = int.Parse(line[1]);
        int K = int.Parse(line[2]);

        int[,] sum = new int[N + 1, M + 1];

        char[] c;

        for (int row = 1; row <= N; row++)
        {
            c = sr.ReadLine().ToCharArray();

            for (int col = 1; col <= M; col++)
            {
                if ((row + col) % 2 == 0)
                {
                    if (c[col-1] == 'W')
                    {
                        sum[row, col] = 1 + sum[row, col - 1] + sum[row - 1, col] - sum[row - 1, col - 1];
                    }
                    else
                    {
                        sum[row, col] = sum[row, col - 1] + sum[row - 1, col] - sum[row - 1, col - 1];
                    }
                }
                else
                {
                    if (c[col-1] == 'B')
                    {
                        sum[row, col] = 1 + sum[row, col - 1] + sum[row - 1, col] - sum[row - 1, col - 1];
                    }
                    else
                    {
                        sum[row, col] = sum[row, col - 1] + sum[row - 1, col] - sum[row - 1, col - 1];
                    }
                }
            }
        }


        int min = 999999999;
        int curr = 0;

        for(int row= K; row<=N; row++)
        {
            for(int col=K; col<=M; col++)
            {
                curr = sum[row,col] - sum[row-K,col] - sum[row,col-K] + sum[row-K, col-K];

                curr = Math.Min(curr, K*K -curr);

                if(curr< min) min = curr;
            }
        }

        Console.Write(min);
    }

}