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

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

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

 

 

 

 

이 문제 풀어도 풀어도 안되길래 검색해봤더니 없어서 어떻게든 설명 글 찾아서 풀어봤습니다!!!!!! 뿌듯하네요!!!

 

https://www.acmicpc.net/board/view/103612

 

여기에 있는 분이 설명해준거 토대로 풀어봤으니

 

여러분도 제꺼 보기 전에 한 번 보고 풀 수 있는지 해보시는게 좋을 거 같아요!!!

 

---

- 문제

 

 

 

체스판이 주어지면 K * K의 크기로 자를때 최소한의 변화로 체스판을 만들 수 있는 경우를 출력하는 문제다.

 

 

 

---

- 해설

 

boardB와 boardW 두개를 이용해서 문제를 해결해야 한다.

 

boardB는 첫번째 위치가 B라고 했을 때 틀린 개수를 저장하는 배열

boardW는 첫번째 위치가 W라고 했을 때 틀린 개수를 저장하는 배열이다.

 

 

 

!!!!!핵심은 틀린 개수이다!!!!!!

 

 

 

1. boardB와 boardW를 다른 누적합 문제처럼 계속 누적해주는데, 틀린 부분이 있을때마다 1씩 증가시켜준다!

 

틀린 부분이 있으면 1 증가시켜주고, 아니면 그냥 그대로 유지하면 된다!!!!!

 

4 4 3
BBBB
BBBB
BBBW
BBWB

 

위와 같은 경우에는 아래와 같이 만들어진다(

boardB[i][j] = boardB[i - 1][j] + boardB[i][j - 1] - boardB[i - 1][j - 1] + 1;

)

와 같이 i-1이랑 j-1이 필요하므로 체스판은 index 1부터 시작한다고 가정했다.

boardB
0 0 0 0 0
0 0 1 1 2
0 1 2 3 4
0 1 3 4 5
0 2 4 5 6

boardW
0 0 0 0 0
0 1 1 2 2
0 1 2 3 4
0 2 3 5 7
0 2 4 7 10

 

2. 위와 같이 만들어졌으면, 이걸 이용해서 문제를 해결하면 된다.

 

boardB와 boardW를 이용해서 

 

boardB[i + K][j + K] - boardB[i][j + K] - boardB[i + K][j] + boardB[i][j]

boardW[i + K][j + K] - boardW[i][j + K] - boardW[i + K][j] + boardW[i][j]

K의 크기에 맞게 반복문을 돌리면 정답을 구할 수 있다.

 

혹시 이 방법이 이해가 안된다면 

https://stopthebackspace.tistory.com/108

 

여기 이차원 배열의 누적합을 이용하는 좀 더 쉬운 문제가 있으니 먼저 풀고 오길 바란다.

 

 

 

 

 

근데, 진짜 틀린 개수를 이용하는 방법 같은 걸 생각하는 사람들은 뭐하는 사람들인지 궁금하네요...

 

---

- 풀이

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K, minColor = 100000001, tempB, tempW, smallerTemp;
    char temp;
    cin >> N >> M >> K;
    vector<int> v(M + 1, 0);
    vector<vector<int>> boardB(N + 1, v); // 첫 번째가 B라고 할때 틀린 개수(입력과 같은 이차원 배열)
    vector<vector<int>> boardW(N + 1, v); // 첫 번째가 W라고 할때 틀린 개수

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> temp;
            if ((i + j) % 2 == 1) // 1. 틀릴때마다 1씩 추가해주기
            {
                if (temp == 'B')
                {
                    boardB[i][j] = boardB[i - 1][j] + boardB[i][j - 1] - boardB[i - 1][j - 1] + 1;
                    boardW[i][j] = boardW[i - 1][j] + boardW[i][j - 1] - boardW[i - 1][j - 1];
                }
                else
                {
                    boardB[i][j] = boardB[i - 1][j] + boardB[i][j - 1] - boardB[i - 1][j - 1];
                    boardW[i][j] = boardW[i - 1][j] + boardW[i][j - 1] - boardW[i - 1][j - 1] + 1;
                }
            }
            else
            {
                if (temp == 'B')
                {
                    boardB[i][j] = boardB[i - 1][j] + boardB[i][j - 1] - boardB[i - 1][j - 1];
                    boardW[i][j] = boardW[i - 1][j] + boardW[i][j - 1] - boardW[i - 1][j - 1] + 1;
                }
                else
                {
                    boardB[i][j] = boardB[i - 1][j] + boardB[i][j - 1] - boardB[i - 1][j - 1] + 1;
                    boardW[i][j] = boardW[i - 1][j] + boardW[i][j - 1] - boardW[i - 1][j - 1];
                }
            }
        }
    }
    for (int i = 0; i + K <= N; i++)
    {
        for (int j = 0; j + K <= M; j++) // 2. 틀린 경우가 가장 적은 경우 구하기
        {
            tempB = boardB[i + K][j + K] - boardB[i][j + K] - boardB[i + K][j] + boardB[i][j];
            tempW = boardW[i + K][j + K] - boardW[i][j + K] - boardW[i + K][j] + boardW[i][j];
            smallerTemp = min(tempB, tempW);
            if (minColor > smallerTemp)
            {
                minColor = smallerTemp;
            }
        }
    }
    cout << minColor;

    // cout << "\n\n";                      // 출력 어떻게 되는지 확인하기
    // for (auto a : boardB)
    // {
    //     for (auto aa : a)
    //     {
    //         cout << aa << ' ';
    //     }
    //     cout << '\n';
    // }
    // cout << "\n\n";
    // for (auto a : boardW)
    // {
    //     for (auto aa : a)
    //     {
    //         cout << aa << ' ';
    //     }
    //     cout << '\n';
    // }

    return 0;
}

 

 

---

- 새롭게 알게 된 점