백준 25682 : 체스판 다시 칠하기 2 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Chess(color):
    dp = [[0] * (M + 1) for i in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if (i+j)%2==0:
                value=L[i][j]!=color
            else:
                value=L[i][j]==color
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+value
    count=int(1e9)
    for i in range(1,N-K+2):
        for j in range(1,M-K+2):
            count=min(count,dp[i+K-1][j+K-1]-dp[i+K-1][j-1]-dp[i-1][j+K-1]+dp[i-1][j-1])
    return count

N,M,K=map(int,input().split()) # N=세로 , M=가로

L=[]
for i in range(N):
    L.append(list(input().rstrip()))

print(min(Chess('W') , Chess('B')))

📌 어떻게 접근할 것인가?

2차원 $dp$ 배열을 만들어서 시작점이 $W$ 일때와 $B$ 일때 누적합을 구해준다.

이후 $K×K$ 크기만큼 배열을 탐색해서 누적합의 최소값을 찾는다.

$dp$ 배열의 2차원 누적합은
$dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+value$
으로 계산해준다. 이때 value 는 체스판이 $color$ 와 같으면 1 아니면 0 을 가지게 된다.

value=L[i][j]!=color -> if L[i][j]!=color : value=1 과 같다

$K×K$ 체스판에서의 누적합을 구하는 점화식은
$dp[i+K-1][j+K-1]-dp[i+K-1][j-1]-dp[i-1][j+K-1]+dp[i-1][j-1]$
와 같다. 기존의 누적합 식에 $K$를 넣어주었다.

출력은 print(min(Chess('W'),Chess('B'))) 를 통해 최소값을 구할수 있다.

총 2번의 탐색을 하기때문에 시간초과가 발생할수 있으므로 pypy3 로 제출해야한다.