[백준] 1018번 체스판 다시 칠하기 ★

💡문제접근

• 머릿속으로는 이뤄졌지만 코딩으로 옮기는 과정에서 시간이 많이 걸렸다.
  ①. 8×8 크기의 체스판 모범답안은 2가지로 나눌 수 있다. 하나는 체스판의 좌상단 색깔이 하얀색인 경우, 다른 하나는 체스판의 좌상단 색깔이 검은색인 경우이다.
  ②. 이 때, N과 M의 최댓값은 50이고 다시 칠해야 하는 정사각형의 최대 개수는 64개(cnt)이므로 만약 color_cnt가 64보다 작은 값이라면 최솟값을 갱신해준다.

💡코드(메모리 : 30616KB, 시간 : 100ms)

chess_answer1 = [['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W']]
chess_answer2 = [['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B'],
                 ['B','W','B','W','B','W','B','W'],
                 ['W','B','W','B','W','B','W','B']]

N, M = map(int, input().split())
chess = []
for _ in range(N):
    chess.append(list(input()))

cnt = 64 
for i in range(N-7):
    for j in range(M-7):
        color_cnt = 0
        for a in range(8):
            for b in range(8):
                # 첫 번째) chess_answer1과 비교
                if chess[i+a][j+b] != chess_answer1[a][b]:
                    color_cnt += 1
        if cnt > color_cnt:
            cnt = color_cnt
        color_cnt = 0
        for a in range(8):
            for b in range(8):
                # 두 번째) chess_answer2과 비교
                if chess[i+a][j+b] != chess_answer2[a][b]:
                    color_cnt += 1
        if cnt > color_cnt:
            cnt = color_cnt
print(cnt)

💡소요시간 : 54m