BOJ 1018번: 체스판 다시 칠하기

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

아이디어:

N과 M은 8보다 크거나 작고, 50보다 작거나 같은 자연수이므로

8*8의 가능한 모든 경우를 찾고, 각 경우에 칠해야 하는 정사각형의 최소 개수를 모두 구해도 주어진 ㅅ ㅣ간 내에 해결 가능하다.(브루트포스)

 

8*8 가능한 모든 경우: for (0~N-8)까지 탐색

칠해야 하는 정사각형의 최소 개수: 

칠할 수 있는 경우는 W가 i+j=짝수 이고 B는 i+j 홀수인 경우와, W는 홀수, B는 짝수인 두 가지 경우가 있음.

두 개의 변수를 만들고 W인데 짝수인 경우에는 a에 W인데 홀수인 경우에는 b에 1씩 더한다.(B의 경우도 마찬가지)

둘 중 최솟값 업데이트

 

코드:

import sys
n, m = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(list(sys.stdin.readline().rstrip()))

ans = 25000
for N in range(0, n-7):
    for M in range(0, m-7):
        a=0
        b=0
        for i in range(N, N+8):
            for j in range(M, M+8):
                if (arr[i][j]=='W'):
                    if ((i+j)%2==0):
                        a+=1
                    else:
                        b+=1
                else:
                    if ((i+j)%2==0):
                        b+=1
                    else:
                        a+=1
        ans = min(ans, min(a,b))
print(ans)