체스판 다시 칠하기 2

• 체스판 다시 칠하기를 확장시킨 문제. 체스판 다시 칠하기에서는 K가 8로 고정이었기 때문에, 단순하게 O(M*N*8*8) 알고리즘으로 충분했지만 여기에서는 조금 더 효율적인 알고리즘이 필요하다.
• 사실 이 문제는 1차원 배열에서 고정된 길이의 부분배열들중 합이 최대가 되는 것을 찾는 문제를 2차원으로 확장시킨 문제이다.
• 1차원이었으면, 슬라이딩 윈도우 방식으로 간단하게 구현할 수 있는 문제이지만, 2차원에서는 이 방식을 구현하는 것은 조금 번거롭다..
• 대신 그냥 2차원 누적합을 계산해놓고, 이것을 이용해서 모든 부분구간에 대해서 부분합을 구하는 방식으로 구현했다. 메모리를 좀더 먹고, 속도도 살짝 느리겠지만 이쪽이 구현이 조금 더 간단했다. 어차피 빅오 시간복잡도는 O(NM)으로 동일하다.

"""Solution code for "BOJ 25682. 체스판 다시 칠하기 2".

- Problem link: https://www.acmicpc.net/problem/25682
- Solution link: http://www.teferi.net/ps/problems/boj/25682

Tags: [prefix sum]
"""

import sys


def main():
    # pylint: disable=unused-variable
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    board = [sys.stdin.readline().rstrip() for _ in range(N)]

    prefix_sum = [[0] * (M + 1)]
    for row, psum_row_prev, target in zip(board, prefix_sum, 'BW' * N):
        psum_row_cur = [0]
        rsum = 0
        for ch, ps in zip(row, psum_row_prev[1:]):
            rsum += ch == target
            target = 'B' if target == 'W' else 'W'
            psum_row_cur.append(ps + rsum)
        prefix_sum.append(psum_row_cur)

    answer = K * K
    for beg, end in zip(prefix_sum, prefix_sum[K:]):
        for bb, be, eb, ee in zip(beg, beg[K:], end, end[K:]):
            s = ee - be - eb + bb
            answer = min(answer, s, K * K - s)

    print(answer)


if __name__ == '__main__':
    main()