[백준 파이썬] 25682 체스판 다시 칠하기 2

📌문제 출처

백준 단계별 문제풀이 - 누적합
https://www.acmicpc.net/problem/25682

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

 

❓ 문제

 

 

 

❗ 풀이

• 제일 가치가 큰 동전부터 최대로 채우기

📗 풀이 코드

import sys
input = sys.stdin.readline
# 체스판이 첫번째 칸과 같은지 다른지 확인하고 누적합을 생성하는 함수
def check_first(first_block):
    # 정상 체스판의 경우 행열 합이 짝수일 때 첫번째 칸과 같은 색이다.
    prefix_sum = [[0 for _ in range(m+1)] for _ in range(n+1)] # (n+1)*(m+1) 이차원 배열 생성
    for i in range(n):
        for j in range(m):
            if (i + j) % 2 == 0: 
                value = board[i][j] != first_block
            else:
                value = board[i][j] == first_block
            prefix_sum[i+1][j+1] = value + prefix_sum[i+1][j] + prefix_sum[i][j+1] - prefix_sum[i][j]
    cnt = prefix_sum[-1][-1]
    for i in range(1,n-k+2): # n-K+1 ~ n칸까지 포함하여 자르면 k칸짜리 체스판이기에 n-k+2가 끝임
        for j in range(1,m-k+2):  
            tmp = prefix_sum[i+k-1][j+k-1] - prefix_sum[i+k-1][j-1] - prefix_sum[i-1][j+k-1] + prefix_sum[i-1][j-1]
            if cnt > tmp :
                cnt = tmp
    return cnt

n,m,k = map(int,input().split())
board = [list(input().strip()) for _ in range(n)] # ['B','B','B','B'] 형태로 넣어줌
print(min(check_first('W'),check_first('B')))

📗 코드 해설

• 정상적인 체스판의 경우 모든 칸에 대해 각각 칸의 행과 열 번호의 합에 따라 맨 왼쪽 위의 칸과 같은 색인지 아닌지 판단이 가능
  - 행+열이 짝수라면 맨 왼쪽 위의 칸과 동일한 색 / 홀수라면 다른 색
• 맨 왼쪽 위의 칸이 흰색(또는 검은색)일 때 정상적인 체스판과 대조하여 색이 다른 칸이 얼마나 있는지를
  2차원 누적합으로 체스판을 변경
• 누적합으로 변경된 체스판의 모든 K*K 크기에 대한 누적합을 확인하여 최소값을 출력