[Baekjoon - 25682] 체스판 다시 칠하기 2

난이도: Gold V

 

태그

• Prefix Sum (Multidimensional)

풀이

0. Notation

• \( A \) : 입력받은 보드. 세로가 \( N \)칸, 가로가 \( M \)칸이다.
• \( C \): 체스판 무늬를 띄고 있는 보드 (우측 상단의 칸은 Context에 따라 달라질 수 있음)

1. \( K \times K \)로 잘려져 있는 체스판을 칠하는 데 필요한 최소 비용은?

다르게 말하자면, \( A \)가 이미 \( K \times K \)일 때를 의미합니다.

 

이 경우, 체스판의 무늬가 어떻게 되었든, \( A_{i, j} = C_{i, j} \)라면 그 칸은 칠하지 않고 놔둘 수 있습니다.

하지만, \( A_{i, j} \neq C_{i, j} \)라면 그 칸을 새로 칠해야만 합니다.

 

따라서, \( A_{i, j} \neq C_{i, j} \)인 칸의 개수만 세면 됩니다.

 

실제로 만들 수 있는 체스판의 무늬는 구석의 칸 색깔에 따라 2가지 경우로 나뉘므로, 이 2가지 경우에 대해 모두 계산해주면 됩니다.

2. \( A \)를 자르지 말고, \( C \)를 확장한다면?

\( A \)를 \( K \times K \)로 자르는 문제를 만드는 대신, \( C \)를 패턴을 유지하면서 \( N \times M \) 크기로 확장해봅시다. 체스판의 무늬의 특성상, 확장 방식은 유일합니다.

 

확장된 \( C \)의 특징으로는 무엇이 있을까요? 바로 임의의 \( K \times K \) 크기의 보드를 잘라도 체스판 무늬가 뜬다는 것입니다. /* 사실 $K \times K$ 뿐만 아니라, 임의의 $A \times B$에 대해 모두 성립합니다. */

3. ([2]에서 이어짐) 확장된 \( C \)를 원하는 대로 자를 수 있으니까...?

[1]에서 말했던 점을 잊지 맙시다. 체스판의 무늬가 어떻게 되든, 결국 우리가 세야 하는 건 \( A_{i, j} \neq C_{i, j} \)인 칸의 개수입니다.

하지만 [1]의 상황과는 달리, \( K \times K \) 크기의 체스판을 직접 잘라야 하겠죠. 다르게 말하자면, \( [y, y+K-1] \times [x, x+K-1] \) 의 부분 배열에 대한 답을 구해야 하는 거죠.

 

원하는 직사각형 부분 배열에 대해, 무언가의 합을 구하는 문제는 2차원 누적 합을 사용해서 해결할 수 있습니다. 그러니 이를 사용해봅시다.

 

아래와 같은 배열 \( B_{i, j} = (1 \text{ if } A_{i, j} \neq C_{i, j} \text{, } 0 \text{ otherwise}) \)를 정의해봅시다.

그리고, 이의 2차원 누적합 \( P_{i, j} = \sum\limits_{y=1}^{i} \sum\limits_{x=1}^{j} B_{y, x} \)를 정의해봅시다.

2차원 누적합을 사용하면 원하는 직사각형 부분 배열에 대한 \( B_{i, j} \)의 합을 구할 수 있습니다.

다르게 말하자면, \( A_{i, j} \neq C_{i, j} \)인 칸의 합, 또는 칸의 개수를 구할 수 있습니다.

 

따라서, 이대로 문제를 풀 수 있습니다...?

4. [3]으로 해치운 건가?

잠깐 제대로 확인해봅시다.

 

\( C \)를 확장한다는 걸로 끝날까요? 생각을 조금 깊게 해보면, 같은 체스판 무늬 \( C \)에서 확장을 한다고 해도, 이 뒤에 다시 \( K \times K \) 크기의 체스판을 잘라서 나온 결과가 다시 원래의 \( C \)가 되지는 않을 수 있습니다. /* 물론 체스판의 무늬는 나오겠죠. 하지만 이게 정확히 \( C \)였는가? 라고 묻는 건 다른 질문입니다. */

 

그러니, 하얀색으로 시작하는 체스판 무늬 \( C \)과 검은색으로 시작하는 체스판 무늬 \( C' \)을 각각 확장한다고 해도, 이를 다시 자르면 \( C \)와 \( C' \)이 나오지 않아서 제대로 모든 경우를 확인하지 못할 수도 있습니다.

 

하지만 다행히도 이런 경우가 발생하지는 않습니다. 이유는 체스판의 무늬 상, 항상 \( C_{i, j} \neq C'{i, j} \)이기 때문이죠. 즉, 만약 \( C \)를 확장하고 잘라서 나온 결과가 \( C' \)이라면, 이 과정을 \( C' \)에 동일하게 적용하면 \( C \)가 나오게 됩니다. 따라서, 무슨 무늬가 \( C \)이고 \( C' \)인지 몰라도, 결국 두 경우 모두 확인하게 된다는 의미죠.

5. (추가) 조금 더 해볼 수 있지 않을까요?

사실 [4]까지만 생각해도, 2차원 누적합을 \( B \)와 \( B' \)에 대해 따로 만들어서 해결할 수 있습니다.

 

하지만, \( C_{i, j} \neq C'_{i, j} \)라는 점을 생각해보면 /* 사실 색깔이 2가지밖에 없다는 것도 생각해야 하지만요 */, \( B'_{i, j} = 1 - B_{i, j} \)입니다. 따라서, 이의 누적합 역시 \( P'_{i, j} = (i \cdot j) - P_{i, j} \)가 되죠.

 

즉, \( B \)와 이의 누적합 \( P \)만 만들어도, 이를 토대로 \( B' \)과 \( P' \)을 유추할 수 있으니 그냥 \( B \)와 \( P \)만 만들어서 문제를 해결할 수 있습니다.

구현

int arr[2020][2020], prf[2020][2020]; // B, P
inline int sum(int y1, int x1, int y2, int x2){ // 2D prefix sum, query
    return prf[y2][x2] - prf[y2][x1-1] - prf[y1-1][x2] + prf[y1-1][x1-1];
}
 
void Main(){
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            char c; cin >> c;
            if ((c=='B') == ((i^j)&1)){ arr[i][j] = 1; } // Chessboard
        }
    }
    // 2D prefix sum, init
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            prf[i][j] = prf[i-1][j] + prf[i][j-1] - prf[i-1][j-1] + arr[i][j];
        }
    }
    int ans = k*k;
    for (int i = 1; i <= n-k+1; i++){
        for (int j = 1; j <= m-k+1; j++){
            int res = sum(i, j, i+k-1, j+k-1); // prefix sum
            ans = min({ans, res, k*k-res}); // minimum of P, and P'
        }
    }
    cout << ans;
}