[백준] 25682 체스판 다시 칠하기 2, python

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

 

 

 

 

 

n*m크기의 체스판을 k*k크기로 나누었을 때 각 칸을 체스판 형태로 만들려고 한다. 이때 색을 칠하는 횟수의 최솟값을 구하는 문제이다.

 

 

dp [i][j][0]를 i, j 번째 칸을 W일 때 칠한 횟수의 최솟값,

dp [i][j][1]을 i, j번째 칸이 B일 때 칠한 횟수의 최솟값이라고 한다.

 

dp [i번째][j번째][해당칸의 색깔(W면 0, B면 1)] = dp [i번째][j-1번째][해당칸의 색깔과 반대색] + dp [i-1번째][j번째][해당칸의 색깔과 반대색] - dp [i-1번째][j-1번째][해당칸의 색깔과 같은 색] + 기존 색과 같으면 1 아니면 0을 해주면 된다.

 

 

 

i, j 번째 칸이 W인 경우

 

현재 칸이 그대로 놔두고 칠한 최소 횟수

dp [i][j][0]    =   dp [i-1][j][1]   +    dp [1][j-1][1]   -   dp [i-1][j-1][0]   +   0 

 

현재 칸을 B로 바꾸고 칠한 최소 횟수

dp [i][j][1]    =   dp [i-1][j][0]   +    dp [1][j-1][0]   -   dp [i-1][j-1][1]   +  1

 

 

이렇게 dp의 i, j를 n-1, m-1까지 채워주면 된다.

 

 

 

 

 

 

이제 바둑판을 k*k로 나누어 그 안에서 칠한 횟수의 최솟값을 구해야 한다.

k=3의 경우

 

i, j까지 칠한 횟수에서 해당 그림에 있는 부분을 칠한 횟수만큼 빼주면 된다.

 

 

 

 

 

 

 

여기서 주의할 점은 k가 홀수이면 제외되는 부분의 끝이 i, j 칸의 색과 달라야 하고, k가 짝수라면 같아야 한다.

 

 

 

 

 

import sys
input = sys.stdin.readline

n,m,k = map(int, input().split())
board = [[x for x in input().rstrip()] for _ in range(n)]

answer = 10**16

# i,j번째 칸(W일경우 0 B일경우 1) 일 경우 칠해야하는 횟수
dp = [[[0]*2 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        paint_w,paint_b = 10**16,10**16
        if board[i-1][j-1] == 'W':
            # 현재칸이 W인경우, 그대로 놔두는경우, B로 바꾸는 경우의 최솟값
            paint_w = dp[i][j-1][1] + dp[i-1][j][1] - dp[i-1][j-1][0] 
            paint_b = dp[i][j-1][0] + dp[i-1][j][0] - dp[i-1][j-1][1] + 1
        elif board[i-1][j-1] == 'B':
            # 현재칸이 B인경우, 그대로 놔두는경우, W로 바꾸는 경우의 최솟값
            paint_w = dp[i][j-1][1] + dp[i-1][j][1] - dp[i-1][j-1][0] + 1
            paint_b = dp[i][j-1][0] + dp[i-1][j][0] - dp[i-1][j-1][1]
        dp[i][j][0] = paint_w
        dp[i][j][1] = paint_b

def paint(i,j):
    # i,j번째 칸이 W인경우 k가 짝수인경우 같은색, 홀수인경우 다른색
    paint_w = dp[i+k][j+k][0] - dp[i][j+k][k%2] - dp[i+k][j][k%2] + dp[i][j][0]
    # i,j번째 칸이 B인경우
    paint_b = dp[i+k][j+k][1] - dp[i][j+k][1-k%2] - dp[i+k][j][1-k%2] + dp[i][j][1]
    return min(paint_w,paint_b)

# 체스판을 나눌수있는 모든 경우에 대해 탐색
for i in range(n-k+1):
    for j in range(m-k+1):
        answer = min(answer, paint(i,j))

print(answer)