25682번 체스판 다시 칠하기2 (Gold5)

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

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

n,m,k=map(int,input().split())

blackBoard=[[0 for _ in range(m+1)] for _ in range(n+1)]
whiteBoard=[[0 for _ in range(m+1)] for _ in range(n+1)]

black=True
white=False

array=[]
for i in range(n):
    array.append(list(input()))
    for j in range(m):
        if array[i][j]=='B': array[i][j]=1
        else: array[i][j]=0

for i in range(1,n+1):
    for j in range(1,m+1):
        blackBoard[i][j]=black
        whiteBoard[i][j]=white
        black=not black
        white=not white
    if m%2==0:
        black = not black
        white = not white

for i in range(n):
    for j in range(m):
        blackBoard[i+1][j+1]^=array[i][j]
        whiteBoard[i+1][j+1]^=array[i][j]

prefixBlackBoard=[[0 for _ in range(m+1)] for _ in range(n+1)]
prefixWhiteBoard=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        prefixBlackBoard[i+1][j+1]=prefixBlackBoard[i][j+1]+prefixBlackBoard[i+1][j]\
                             -prefixBlackBoard[i][j]+blackBoard[i+1][j+1]
        prefixWhiteBoard[i+1][j+1]=prefixWhiteBoard[i][j+1]+prefixWhiteBoard[i+1][j]\
                             -prefixWhiteBoard[i][j]+whiteBoard[i+1][j+1]

minimum=int(1e9)
for i in range(n-k+1):
    for j in range(m-k+1):
        minimum=min(minimum,prefixBlackBoard[k+i][k+j]-prefixBlackBoard[i][k+j]
                    -prefixBlackBoard[k+i][j]+prefixBlackBoard[i][j])
        minimum=min(minimum,prefixWhiteBoard[k+i][k+j]-prefixWhiteBoard[i][k+j]
                    -prefixWhiteBoard[k+i][j]+prefixWhiteBoard[i][j])
print(minimum)

접근방법

1. 주어진 입력을 2차원 배열로 만든다.(B=True, W=False)

2. 맨왼쪽 위가 검정으로 시작하는 체스판인 blackBoard와, 흰색으로 시작하는 체스판인 whiteBoard를 각각 생성한다.

3. 처음 입력으로 생성한 2차원 배열과 blackBoard, whiteBoard를 각각 XOR 연산하여 새로운 2차원 배열을 만든다.

4. 만들어진 2개의 배열을 각각 누적합한 prefixBoard를 구한다.

5. prefixBoard에서 적용 가능한 모든 k*k의 구간합을 구하고, 최소 값을 출력한다.