[C++] 백준 - 25682번 문제

25682번: 체스판 다시 칠하기 2 (acmicpc.net)

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

 

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

---

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

1018번 문제를 누적합으로 풀어내는 문제입니다.

 

고려할 사항들은 다음과 같습니다.

 

1. 체스판은 두 종류 뿐입니다.

 

0, 0 지점이 W거나 B거나

 

 

 

2. (0, 0) 이 W인 체스판의 칠해야 할 갯수 = 체스판의 총 사각형 갯수 - B인 체스판의 갯수입니다.

 

즉, 한 쪽 체스판의 갯수만 구하면 나머지 갯수는 쉽게 구할 수 있습니다.

 

예시)

 

W 체스판 기준

 

WB  => 1개

BB

 

B 체스판 기준

 

WB  => 3개

BB

 

3. 누적합은 바꿔야할 사각형 갯수를 기준으로 더해나갑니다.

 

가로로 한번, 세로로 한번 더해줍니다.

 

예시) W 체스판 기준

 

 

 

4. 구하고자 하는 영역의 바꿀 사각형 갯수를 구하는 방법은

 

 

빨간 원은 더하고 파란 원은 뺍니다.

 

예시의 빨간 사각형 4개의 경우 

 

1 + 3 - 2 - 2 = 0으로

 

W 체스판 기준으로 바꿀 사각형이 하나도 없음을 알 수 있습니다.

(B 체스판 기준이면 4 - 0 = 4개 만큼 사각형을 바꿔 칠해야 합니다.)

 

왜 이렇게 더하고 빼야하는지는 누적합의 성질을 참고하세요.

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);

    //누적합 배열
    vector<vector<int>> arr(N + 1, vector<int>(M + 1, 0));

    //0, 0을 W 기준으로 작성 바꿔야할 타일 개수를 누적합 저장
    for(int y = 1; y <= N; y++)
    {
        char input[2001];
        scanf("%s", input);
        for(int x = 1; x <= M; x++)
        {
            //가로로 누적합
            if(input[x - 1] == 'B')
                arr[y][x] = arr[y][x - 1] + ((x + y) % 2 == 0);
            else
                arr[y][x] = arr[y][x - 1] + ((x + y) % 2 == 1);

            //세로로 누적합
            arr[y][x - 1] += arr[y - 1][x - 1];
        }
    }

    //누락된 마지막 열 세로로 누적합
    for(int y = 1; y <= N; y++)
        arr[y][M] += arr[y - 1][M]; 

    int const max_count = K * K;
    int ans = max_count;

    //누적합에서 바꿀 사각형 갯수 계산
    for(int y = K; y <= N; y++)
    {
        for(int x = K; x <= M; x++)
        {
            int summ = arr[y][x] + arr[y - K][x - K];
            summ -= arr[y][x - K] + arr[y - K][x];

            //WB 반전한 경우 고려
            ans = min(ans, min(summ, max_count - summ));
        }
    }
    printf("%d", ans);
    return 0;
}

 

그 외

---