백준 1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

생각보다 어려워서 꼼꼼히 풀어보려고 블로그에 남긴다.

 

n,m = map(int,input().split())
board = []
count = []
for _ in range(n):
    board.append(input())

for i in range(n-7):
    for j in range(m-7):
        black_paint = 0
        white_paint = 0
        for a in range(i,i+8):
            for b in range(j,j+8):
                if (a+b)%2==0:
                    if board[a][b]!='W':
                        black_paint +=1
                    if board[a][b]!='B':
                        white_paint +=1
                else:
                    if board[a][b]!='B':
                        black_paint +=1
                    if board[a][b]!='W':
                        white_paint +=1
        count.append(min(black_paint,white_paint))

print(min(count))

 

큰 직사각형 board를 받아오면 8x8의 고정된 정사각형을 먼저 다른다음에

체크무늬를 가장 적게 칠할 수 있는 경우를 구하는 것

 

일단 board를 list에 기억해두고 8x8로 잘라서 검사를 하는것이 중요하다고 생각하였다.

for i in range(n-7):
    for j in range(m-7):
        black_paint = 0
        white_paint = 0
        for a in range(i,i+8):
            for b in range(j,j+8):

n-7,m-7로 하면 8x8로 자를때의 좌측상단의 시작점을 index 오류없이 시작할 수 있어서 저 방법을 선택하였고

8x8를 하기 위해 i+8, j+8를 하였다.

black_paint, white_paint는 좌측상단이 'W','B'로 시작할 경우 색칠한 체스판의 개수를 세기위한 변수이다.

                if (a+b)%2==0:
                    if board[a][b]!='W':
                        black_paint +=1
                    if board[a][b]!='B':
                        white_paint +=1
                else:
                    if board[a][b]!='B':
                        black_paint +=1
                    if board[a][b]!='W':
                        white_paint +=1
        count.append(min(black_paint,white_paint))

리스트에 index의 합이 짝수와 홀수로 나눈경우가 체크무늬에 해당하기 때문에 저런 조건식을 넣어주면서 

한개의 8x8 정사각형이 끝날때마다 작은값을 리스트에 넣고 마지막에 최종적으로 또 최소값을 출력해준다.