25682. 체스판 다시 칠하기 2

tose33 2023. 10. 13. 13:24

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

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

체스판 다시 칠하기 1 은 모든 경우를 다 구하는 브루트 포싱을 해도 시간초과가 나지 않는다.

이 문제는 그렇게 하면 시간초과다.

백준 1018. 체스판 다시 칠하기

www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어

tose33.tistory.com

d[0][i][j] : 좌표 i,j 가 마지막인 KxK 크기의 'B' 로 시작하는 체스판을 만들었을때 칠해야 하는 'W' 의 갯수.

d[1][i][j] : 좌표 i,j 가 마지막인 KxK 크기의 'W' 로 시작하는 체스판을 만들었을때 칠해야 하는 'B' 의 갯수.

d[color][i][j] = d[color][i-1][j] + d[color][i][j-1] - d[color][i-1][j-1]

if 현재 칸 (i,j) 를 반대 색으로 칠해야 한다면 d[color][i][j]++;

즉 [1][1] ~ [i][j] 까지 봤을때 몇 개의 칸을 칠해야 하는지 구한다.

B로 시작하는 보드 W로 시작하는 보드 두가지가 있기 때문에 두가지 모두 구해야 한다.

예를들어 문제의 예제1의 경우 아래의 각 칸은값은 [1][1]~[i][j] 크기의 직사각형을 B로 시작하는 보드처럼 만드는데 칠해야 하는 칸의 갯수다.

누적합을 구하고 나면 KxK 크기로 잘라보면 된다.

d[B][i][j] - (d[B][i][j - K] + d[B][i - K][j]) + d[B][i - K][j - K]