백준 25682 : 체스판 다시 칠하기

맨 처음이 W로 시작하는 "조건 만족 전체 사이즈 체스판"과 B로 시작하는 "조건 만족 전체 사이즈 체스판"을 미리 구해두고,필요 색칠 횟수를 값으로 삼는 누적합을 미리 구해둔 뒤, 그걸 활용하여 체스판을 자르는 모든 경우의 수를 돌면서 최소 색칠 횟수를 구한다.

임의의 K*K 크기에서 색칠 횟수를 구할 때 왼쪽 윗 부분에서 한 칸씩 전의 idx를 사용하기 때문에, 편의를 위해 idx의 시작을 1부터로 통일한다.

check는 모든 칸이 조건을 충족하는 체스판을 나타낸 것이다.sum_sub는 (1, 1)부터 (x, y)까지의 체스판의 색칠 횟수 값을 담는 2차원 리스트이다.

체스판을 자르는 모든 경우의 수를 돌면서 누적합을 이용하여 가장 적은 색칠 횟수를 찾는다.