사용 언어: python 3.9.1

❓ Problem

백준 링크

📕 피드백

1. 발전 방향

반례를 찾자...

2. 느낀점

무턱대고 하는 것보다, 테스트 케이스로 적힌 것을 그려 보면서 어느 정도 이해하고 하는 게 좋다고 생각함. 이게 훨씬 시간 절감. 즉, 문제를 이해하는 시간이 어느 정도 필요하다고 생각함.

🚩 Solution

1. 접근법

TRY 1

매 i, j 후보마다 해당 범위 내의 칠하는 부분을 체크해서(8*8) 더하기

→ 오류: cntB와 cntW 두개로 나뉘어야 한다고 함.

이유 = 왼쪽 위가 블랙이고, 나머지는 왼쪽 위만 바꾸면 되는.. 그런 구성일 수 있기 때문. 즉, 왼쪽 위는 고정값이 아니기 때문!

예를 들어, 왼쪽 위=블랙이고, 나머지는 [<왼쪽 위=흰색>일 때 타일 칠할 게 없는 구성]일 수 있음.

TRY 2

따라서 왼쪽 위에서부터 어느 j, i번쨰 인덱스가 짝수만큼 먼 경우

• 짝수만큼 먼 인덱스에
  • b로 규칙을 맞춰 색칠하게 되는 경우 = b_cnt
  • w로 규칙을 맞춰 색칠하게 되는 경우 = w_cnt

→ 그래서 b_cnt, w_cnt 중 나중에 덜 추가되는 걸로.

2. 코드

def main():
    M,N = map(lambda i: int(i), input().split())
    board = list(map(lambda i: input(), range(M)))
    BMIN = 100; WMIN = 100

    for i in range(N-8+1):
        for j in range(M-8+1):
            bcnt = 0; wcnt = 0; f_val = board[j][i]
            for x in range(i, i+8):
                for y in range(j, j+8):
                    if ((x+y-(i+j)) % 2) == 0:
                        # i,j 로부터 짝수만큼 떨어져 있음
                        if board[y][x] == 'B':
                            wcnt += 1
                        else:
                            bcnt += 1
                    else:
                        if board[y][x] == 'B':
                            bcnt += 1
                        else:
                            wcnt += 1
                    
            BMIN = min(bcnt, BMIN)
            WMIN = min(wcnt, WMIN)

    return min(BMIN, WMIN)

print(main())

3. 결과

시간 복잡도 분석

$O(M*N*8*8)$