[BOJ, Python] 25682 - 체스판 다시 칠하기 2 ( with DP )

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

 

백준 단계별로 풀어보기 문제가 업데이트되면서 누적합 카테고리에 새롭게 추가된 Gold 5 난이도의 누적합 문제이다. 앞 선 문제인 1018 - 체스판 다시 칠하기의 브루트 포스 알고리즘과 2차원 배열의 누적합 DP를 활용하면 무난하게 AC를 받을 수 있다. 다만 반복문을 작성할 때에는 최대한 한 반복문 안에 여러 연산을 실행할 수 있게 코드를 짜주는 것이 좋다. 해당 예제 코드보다 더 효율적인 코드가 가능해 보이기도 하다.

# 빠른 입출력
import sys
input = sys.stdin.readline
row, column, size = map(int, input().split())

# 두 종류의 체스판 중 하나만 사용
arr = [["W" if (i + j) % 2 == 0 else "B" for i in range(column) ] for j in range(row)]

# 예시 체스보드
test = list()

# arr과 test보드를 비교하여, 바꿔줘야 할 칸에 1을 할당시킬 예정
cmp = [[0 for _ in range(column)] for _ in range(row)]

# 2차원 배열의 부분 누적합을 담을 배열
ss = [[0 for _ in range(column + 1)] for _ in range(row + 1)]

for i in range(row):
    test.append(list(map(str, input())))
    # 바꿔줘야 할 칸에 1을 할당하고,
    for j in range(column):
        if arr[i][j] != test[i][j]:
            cmp[i][j] = 1
        # 해당 칸까지의 누적합을 할당
        ss[i + 1][j + 1] = ss[i][j + 1] + ss[i + 1][j] - ss[i][j] + cmp[i][j]

# 정답은 체스판의 크기를 넘을 수 없으므로, 체스판의 크기로 정답을 초기화
ans = size * size

# 브루트포스 알고리즘을 활용하여, 부분 누적합 중 가장 작은 값으로 대체
for i in range(size, row + 1):
    for j in range(size, column + 1):
        case = ss[i][j] - ss[i - size][j] - ss[i][j - size] + ss[i - size][j - size]
        ans = min(ans, case, size * size - case)
        
# 정답 출력
print(ans)