Baekjoon 25682. 체스판 다시 칠하기 2 / Python

25682. 체스판 다시 칠하기 2

난이도 : 골드 4
소요 시간 : 20분
날짜 : 2025.01.06
언어 : 파이썬
알고리즘 유형 : 누적 합

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 아무렇게나 칠해져있는 n * m 의 판이 있음.
2. 체스판은 검은색, 흰색이 번갈아 칠해져야함.
3. k * k를 잘라서 체스판으로 만드려고 함, 칠해야하는 최소 개수는?

2. 해결 방식

1. 미리 완벽한 체스판을 만들어놓기, (두개 : 왼쪽상단이 검은색, 흰색)
2. 틀린개수의 누적합을 구하기
   • 현재의 틀린개수 = 왼쪽의 틀린개수 + 위쪽의 틀린개수 - 왼쪽 위의 틀린개수 + 현재칸의 틀린지 여부
3. 전체 돌면서 최솟값 확인하기

3. 정답 코드

import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

board = [[1 if i == 'W' else -1 for i in list(input())] for _ in range(n)]

# 완벽 체스판 만들기
# 왼쪽위가 흰색 : chess1 검은색 : chess2
chess1 = [[[1, -1][(i + j)%2] for j in range(m)] for i in range(n)]
chess2 = [[[-1, 1][(i + j)%2] for j in range(m)] for i in range(n)]

# 틀린개수 누적합 하기
res1 = [[0] * (m + 1) for _ in range(n + 1)]
res2 = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n):
    for j in range(m):
        res1[i+1][j+1] = res1[i][j + 1] + res1[i + 1][j] - res1[i][j] + (board[i][j] != chess1[i][j])
        res2[i+1][j+1] = res2[i][j + 1] + res2[i + 1][j] - res2[i][j] + (board[i][j] != chess2[i][j])

ans = 4000000
for i in range(k, n + 1):
    for j in range(k, m + 1):
        ans = min(
            ans,
            res1[i][j] - res1[i-k][j] - res1[i][j-k] + res1[i-k][j-k],
            res2[i][j] - res2[i-k][j] - res2[i][j-k] + res2[i-k][j-k]
        )

print(ans)