백준 25682 체스판칠하기2

체스판칠하기2 (백준 25682)

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

완전탐색 방식으로는 풀었으나,
시간초과가 났기에 다른 방법을 찾아야 했다
누적합, 구간합과 비슷한 생각은 하였으나
결국 스스로 구현할 수 없었기에 다른 예제 코드를 보았다

누적합 : 0~i (특정 요소) 까지의 합
구간합 : 위에서 구한 각 누적합 끼리 빼줌으로서 특정한 구간의 합을 구함
(ex : 누적합 i - 누적합 j 를 통해 i~j 까지의 요소의 합을 구할 수 있음)

2차원 배열에서의 방식은
누적합 : S(i,j) = S(i,j-1) + S(i,j-1) - S(i-1,j-1) + (ij) 이다
(이전의 i-1 위치 및 j-1 위치의 누적합을 더하되, i-1,j-1 위치의 것은 두번 더했으므로 한 번 빼준다
이후 현재 요소를 더해준다)
구간합 : Range(x1, y1, x2, y2) = S(x2, y2) - S(x2, y1 -1) - S(x1 - 1, y2) + S(x1 - 1 , y1 -1)
(특정 위치의 누적값 x2,y2는 0부터 더해진 값이므로
0~x1 및 0~y1 까지의 누적합을 빼준다
다만 이때 x1,y1 위치의 누적합은 두번 빼지게 되므로
한번 더해준다)
(특정 위치의 누적합이 다른 위치의 누적합과 겹칠수 있다는 점을 인식하는 것)

따라서 각 체스판의 누적합을 전체를 돌면서 구해주고
각 요소들을 해당 부분들을 K의 사이즈 만큼 구간합을 구해
가장 작은 값을 반환한다

이 때, 검은색으로 시작했을 때와 하얀색으로 시작했을 때 중
작은 값으로 답을 구해야 한다

Code

import sys
import math

inp = sys.stdin.readline

m, n, k = map(int, inp().split())

board = [inp().strip() for _ in range(m)]

# 시간 초과 중
# 어떻게 하면 이걸 풀 수 있지??
# 일단 브루트 포스로는 시간초과
# 당연히 O(n^4)
# DP로 풀 수 있나?
# '누적합'과 '구간 합'의 개념이 필요한 문제
# '누적합' 은 0부터 특정한 인덱스까지의 합
# '구간합'은 누적합의 특정한 부분끼리 뺌으로서 (ex i와 j)
# 그 사이 요소의 합을 구한다는 것이다

# 따라서 흰색과 검은색 각각의 누적합을 구하고
# 이후, k 사이즈에 대한 구간합을 전체 배열을 돌며 가장 작은 값을 구하는 방식이다
# 일단 양 옆(i+1 과 j+1) 은 s(i,j)에 각 요소를 더한 것과 같다
# 2차원 누적합의 기본 개념은 s(i,j) = s(i-1,j) + s(i,j-1) - s(i-1,j-1) + (i,j) 이다
# 이후, 구간합을 구하고, 그 중 가장 작은 값을 반환한다

def minboardPaintCount(m: int, n: int, k: int, startColor) -> int:
    prefix_sum = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    # 누적합 구하기
    for i in range(m):
        for j in range(n):
            value = 0
            # 결국 다음행이 되면 시작 색이 바뀌어야 하는데 짝수일때와 홀수일때가 다르다 (짝수이면 마지막이 그대로, 홀수이면 마지막과 다르게)
            # 그렇기에 i+j가 짝수라면 해당 요소가 시작 색과 같아야 하며
            # 홀수라면 시작 색과 달라야 한다
            # 아니면 그냥 bool 변수하고 행마다 바꿔주는 방법도 있으나 깔끔하진 않다
            if (i + j) % 2 == 0: 
                value = board[i][j] != startColor
            else:
                value = board[i][j] == startColor

            prefix_sum[i + 1][j + 1] = (
                prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + value
            )

    count = math.inf

    # 구간합 구하기
    for i in range(
        1, m - k + 2
    ):  # for 때문에 +1, 그리고 생성했을때 첫열은 0으로 쓰기위해 배열 크기가 +1 되었으므로 +1
        for j in range(1, n - k + 2):
            # 기존 값과 새로 구한 구간합과 비교
            # 구간 합은 누적합에서 '특정한 부분 끼리 뺀 요소'라는 점을 잊지 말것
            # prefix_sum[i-1][j-1] - prefix_sum[i+k-1][j-1] - prefix_sum[i-1][j+k-1] + prefix_sum[i+k-1][j+k-1]
            # 해당 요소는 결국 i 부터 k 및 j부터 k까지의 누적합 끼리의 뺄샘이다
            # Range(x1, y1, x2, y2) = S(x2, y2) - S(x2, y1 -1) - S(x1 - 1, y2) + S(x1 - 1 , y1 -1) (이것과 같음)
            # x2,y2는 0부터 x2,y2 2차원 배열의 누적합이다 (S(x2, y2))
            # 따라서 0~x1 및 0~y1의 요소들은 빼준다(- S(x2, y1 -1) - S(x1 - 1, y2))
            # 다만 이 때 x1,y1 의 요소가 두번 빼지기에 한번 더해서 올바른 값으로 만든다

            # 기존 누적합 인 prefix_sum[i+k-1][j+k-1] 에서
            # 각 x 축과 y축인 누적합을 빼주되 (- prefix_sum[i+k-1][j-1] - prefix_sum[i-1][j+k-1])
            # 공통된 부분인 [i][j] 부분은 두 번뺏으니 한번 더해주는 것이다 (+ prefix_sum[i-1][j-1])
            count = min(
                count,
                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],
            )

    return count


print(min(minboardPaintCount(m, n, k, "W"), minboardPaintCount(m, n, k, "B")))

해결 아이디어

1. 함수 시작시, 체스판의 시작점부터 다음 요소까지의 누적합을 구한다
   
2. 누적합을 구한 이후 k까지의 누적합을 구하며, 이 중 가장 작은 값을 찾는다
   
3. 각 요소는 시작점이 W 혹은 B로 끝날때 중 가장 작은 값을 반환해야 하므로 두번 함수를 호출