Baekjoon 문제 25682번 체스판 다시 칠하기 2

문제 출처: https://www.acmicpc.net/problem/25682

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

---

문제 분석

해당 문제는 누적합 관련 알고리즘을 풀면서 발견한 문제입니다. 기존의 체스판 다시 칠하기의 최적화 버전으로, 더 큰 사이즈의 보드와 줄어든 시간 제한의 차이가 있습니다. 

Baekjoon 1018번 문제 - 체스판 다시 칠하기

기존 체스판 다시 칠하기는 브루트 포스(brute force) 방식으로, 8 x 8 크기의 체스판을 다시 칠하는 최소 개수를 구하는 문제였습니다. 여기에 8로 고정이었던 체스판의 크기를 k로, 시간 제한을 2초 -> 1초로, 보드의 N과 M의 최대값을 50 -> 2000으로 수정됬습니다. 해당 문제는 시간초과가 주된 관심사입니다. 

따라서 전반적인 코드의 수정이 필요했으며, 새롭게 구상한 알고리즘은 다음과 같습니다:

1. 보드의 왼쪽 상단을 기준으로 잡는다. (B or W)
2. 보드 전체를 기준으로, N x M 체스판을 만든다고 했을 때, 각 행별로 옳지 못한 타일들의 수(cnt)를 기록해야한다:
   1. 각 타일을 훓으면서 이전 값과 현재 값이 다르면, cnt를 1 증가시킨다.
   2. N x M 보드(checkCnts)에 저장된 cnt의 값을 기록한다. 
   3. 새로운 행에 도달할 시 cnt = 0으로 초기화한다. 
   4. 새로운 행의 시작점에 이전 행과 현재 행의 값이 다르다면, cnt를 1 증가시킨다. 
   5. [1~4] 과정 반복
3. 옳지 못한 타일들의 수에 대한 누적합(subSum)을 계산한다.
4. loop를 돌면서 N x M 보드에 K x K 사이즈의 체스판에 대한 옳지 못한 타일들의 수를 구한다.
5. 4번 과정에서 최대값과 최소값을 구한다.
6. 최소값과 $K^2$ - 최대값 중 최소 개수를 출력한다.

6번의 경우 K x K 체스판의 좌상단 시작을 어떤 색깔로 시작하냐에 따라 최소값이 될 수도, $K^2$ - 최대값이 될 수도 있다.

전체적인 Time Complexity는 $O(NM)$이므로, $O(n^2)$으로 구할 수 있습니다. 

---

제출 코드 

#include <iostream>
#include <vector>
#define MAX 2000 + 1
#define ll long long 

using namespace std ;

ll maximum = 0, minmum = 1000000000 ;

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(NULL) ;
    cout.tie(NULL) ;
    vector<vector<bool>> board(MAX, vector<bool>(MAX, false)) ;
    vector<vector<int>> checkCnts(MAX, vector<int>(MAX, 0)) ;
    vector<vector<ll>> subSum(MAX, vector<ll>(MAX, 0)) ;
    int N, M, K ;
    char c ;
    cin >> N >> M >> K ;
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= M ; j++){
            cin >> c ;
            board[i][j] = (c == 'W') ;
        }
    }

    bool prev = board[1][1] ;
    for(int i = 1 ; i <= N ; i++){
        int cnt = 0 ;
        for(int j = 1 ; j <= M ; j++){
            if(board[i][j] != prev)
                cnt += 1 ;
            checkCnts[i][j] = cnt ;
            subSum[i][j] += checkCnts[i][j] + subSum[i-1][j] ;
            prev = !prev ;
        }
        if(M%2 == 0)
            prev = !prev ;
    }

    for(int i = 1 ; i <= N - K + 1 ; i++){
        for(int j = 1 ; j <= M - K + 1 ; j++){
            ll sum = subSum[i+K-1][j+K-1] - subSum[i-1][j+K-1] - subSum[i+K-1][j-1] + subSum[i-1][j-1] ;
            maximum = max(maximum, sum) ;
            minmum = min(minmum, sum) ;
        }
    }
    cout << min(minmum, K*K-maximum) << "\n" ;
    return 0 ;
}

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/BaekJoon/P02822.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다:)