[BOJ][C++] 25682번 체스판 다시 칠하기 2

안녕하세요.

오늘은 백준 25682번: 체스판 다시 칠하기 2(링크)  문제를 풀어보려고 합니다.

 

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

예제 입력

//1
4 4 3
BBBB
BBBB
BBBW
BBWB

//2
8 8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

//3
10 13 10
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

//4
9 23 9
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBWWWWWWWW

 

예제 출력

//1
2

//2
1

//3
30

//4
40

 

제한

시간 제한: 1초

메모리 제한: 256MB

 

---

풀이

체스판 다시 칠하기 문제를 먼저 풀고오면 이해가 더 쉽다.

 

위 문제와 동일하게 맨 왼쪽 위 칸이 흰색(W)이거나 검은색(B)인 경우에 따라 나눠주면 된다.

그러나 모든 경우를 일일히 다 계산하기엔 시간복잡도가 O(N^3)이 나오기에 더 효율적인 방법을 써야한다.

 

이때 누적합을 사용하면 쉽게 풀린다.

 

누적합을 이용해 맨 처음 칸이 W일 때, 맨 왼쪽 위부터 (i,j)까지의 다시 칠해야 하는 칸의 개수를 누적하여 구한다. 마찬가지로 맨 처음 칸이 B일 때도 동일하게 진행한다.

 

구하는 방법은 다음과 같이 누적합 사각형을 더하고 빼는 식이다.

 

이후 i=0~n-k, j=0~n-k에 대해 K * K 크기의 보드칸을 검사해야한다.

이전에 구한 누적합을 사용하면 (i,j) 부터 (i+k,j+k)까지의 보드칸의 다시 칠해야 하는 칸의 개수를 구할 수 있다.

 

위에서 누적합을 구한 것처럼 누적합 사각형을 더하고 빼주면 구간합을 구할 수 있게 된다.

정답

코드에서는 예외처리를 쉽게 하기 위해 dp배열을 1부터 시작하도록 수정했다.

#include <iostream>
using namespace std;
using ll = long long;
int n, m, k;
char arr[2001][2001];
int dp[2][2001][2001] = { 0 };
// dp[0]: 맨 처음이 B일 때 고쳐야 되는 개수
// dp[1]: 맨 처음이 W일 때 고쳐야 되는 개수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int idx = (i + j) % 2;
            int ba = (arr[i][j] == 'B');
            int wa = (arr[i][j] == 'W');
            dp[0][i+1][j+1] = dp[0][i+1][j] + dp[0][i][j+1] - dp[0][i][j] + (idx == 0 ? wa : ba);
            dp[1][i+1][j+1] = dp[1][i+1][j] + dp[1][i][j+1] - dp[1][i][j] + (idx == 0 ? ba : wa);
        }
    }

    int ans = 2000*2000+2000;
    for (int i = 0; i <= n - k; i++) {
        for (int j = 0; j <= m - k; j++) {           
            int fb = dp[0][i + k][j + k] - dp[0][i][j + k] - dp[0][i + k][j] + dp[0][i][j];
            int fw = dp[1][i + k][j + k] - dp[1][i][j + k] - dp[1][i + k][j] + dp[1][i][j];
            int tmp = min(fb, fw);
            ans = min(ans, tmp);
        }
    }
    cout << ans;
    return 0;
}

---

이렇게 해서 백준  25682번 체스판 다시 칠하기 2문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!