문제
https://www.acmicpc.net/problem/25682
풀이
- M * N 크기의 보드
- K * K 크기의 체스판으로 만들려고 함
- 다시 칠해야 하는 칸의 최소 개수
체스판은 2가지 종류가 있습니다.
시작이 흰색인 체스판과 검은색인 체스판
그리고 (행 + 열) 인덱스가 짝수일 때 시작 칸의 색이 같아야 하고 홀수일 경우는 달라야 합니다.
이를 가지고 다시 칠해야 하는 칸과 칠하지 않아도 되는 칸을 구분해야 합니다.
전체 보드를 순회하며 칠해야 하는 칸의 개수를 더해주고 그 중 최소값을 구해봤습니다.
누적합 배열을 생성하고 입력된 전체 보드를 순회하여 누적합을 해보겠습니다.
우선 저는 보드판의 첫 시작이 흰색일 때를 기준으로 코드를 작성했습니다.
# 바꿔야 할 보드 개수(누적합 배열)
change = [[0] * (m+1) for _ in range(n+1)]
# 누적합 계산
for i in range(1, n+1):
for j in range(1, m+1):
tmp = board[i-1][j-1] # 현재 보드판의 위치
color = 'W' if (i+j) % 2 == 0 else 'B' # (처음 칸이 흰색 기준)짝수 인덱스일 때 "W"
add = 1 if tmp != color else 0 # 현재 보드판의 위치의 색이 올바르지 않을 경우 누적합 +1
change[i][j] = change[i-1][j] + change[i][j-1] - change[i-1][j-1] + add- tmp: 현재 보드판의 위치(반복문이 1부터 시작하므로 i-1)
- color: 행+열의 인덱스가 짝수일 경우 W, 홀수일 경우 B
- add: 현재 보드판의 위치와 그 위치의 색이 다를 경우 1, 같을 경우 0
- change[i][j]: 누적합을 이용해 값을 선언하고 뒤에 add를 추가했습니다.(칠해야 할 경우 1을 추가해야 되므로)
이 누적합 배열을 이용해 k*k 영역의 다시 칠해야 하는 횟수 계산 후, 최소값을 추출하면 됩니다.
# k*k 영역의 다시 칠해야 하는 횟수 계산
for i in range(k,n+1):
for j in range(k,m+1):
white = change[i][j] - change[i-k][j] - change[i][j-k] + change[i-k][j-k]
black = k * k - white
res = min(res, white, black)- white: k*k 사이즈의 흰색으로 바꿔야 되는 횟수
- black: 전체 사이즈(k*k) - 흰색 칸의 개수
코드
# pypy3
import sys
input = sys.stdin.readline
# 입력
n,m,k = map(int,input().split())
board = [input().rstrip() for _ in range(n)]
# 바꿔야 할 보드 개수(누적합 배열)
change = [[0] * (m+1) for _ in range(n+1)]
# 누적합 계산
for i in range(1, n+1):
for j in range(1, m+1):
tmp = board[i-1][j-1] # 현재 보드판의 위치
color = 'W' if (i+j) % 2 == 0 else 'B' # (처음 칸이 흰색 기준)짝수 인덱스일 때 "W"
add = 1 if tmp != color else 0 # 현재 보드판의 위치의 색이 올바르지 않을 경우 누적합 +1
change[i][j] = change[i-1][j] + change[i][j-1] - change[i-1][j-1] + add
# 결과
res = 1e9
# k*k 영역의 다시 칠해야 하는 횟수 계산
for i in range(k,n+1):
for j in range(k,m+1):
white = change[i][j] - change[i-k][j] - change[i][j-k] + change[i-k][j-k]
black = k * k - white
res = min(res, white, black)
print(res)