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

문제 설명

1. N, M크기의 체스판이 주어진다.

2. 8x8크기로 잘라서 위아래양옆으로 다른 색깔이 와야 한다.

3. 최소한으로 체스판을 칠하려면 어떻게 해야 하는지 구하면 된다.

풀이 과정

 1. 간단한 브루트포스 문제이다.

 2. 먼저 체스판의 색은 두 개이기 때문에 브루트포스를 진행하기 앞서 bit로 처리하기 위해 boolean값으로 바꾸어 준다. 물론 그냥 시간복잡도를 줄이기 위함으로 굳이 바꾸지 않아도 된다.

 3. 전체 크기를 0,0위치를 기준으로 오른쪽, 아래 8칸씩 짤라서 진행한다. 체스판의 최대 X축의 길이가 N이라고 하면 N-8까지 잘라서 구하면 된다.

 4.  여기서 나는 조금 새로운 방법으로 문제를 해결했다.

 -> 자르는 기준이 된 체스판의 기준으로 상하좌우는 그것과 달라야 한다.

 -> (0, 0)을 기준으로 한다면 (0, 1) (1, 0)은 이와 달라야 한다.

 -> 그리고 (0, 1)을 기준으로 한다면 (0, 2) (1, 1)은 이와 달라야 한다.

모두 다른 방법은 이렇게 된다.

W(0, 0)	B(0, 1)	W(0, 2)	B(0, 3)
B(1, 0)	W(1, 1)	B(1, 2)	W(1, 3)
W(2, 0)	B(2, 1)	W(2, 2)	B(2, 3)
B(3, 0)	W(3, 1)	B(3, 2)	W(3, 3)

 -> 여기서 생각해 보면, 왼쪽 맨 위 위치인 W를 기준으로 (0,1)(0,3)(1,0)(1,2)(2,1)(2,3)....이렇게는 다르게, (0,2)(1,1)(1,3)(2,0)(2,2)(3,

1)...이렇게는 같게 나온다.

 -> 그렇다면 현재위치 기준 홀수만큼의 거리가 떨어진 경우는 달라야 하고, 짝수만큼의 거리가 떨어진 경우 같아야 한다는 것이다.

 -> 즉, 현재 위치의 색을 고른 후, FOR문을 8X8에 대해 진행하며 x축과 y축의 거리의 합이 홀수인 동시에 값이 같거나, 거리의 합이 짝수인 동시에 값이 다른 값들을 더해주면 총 변경하는 갯수를 구해 줄 수 있다.

 5. 그렇게 구한 전체 변경 수를 구해주면 되는데, 여기서 주의할 점이 있다.

-> 생각해 보면 만약 (0, 0)의 위치에 있는 값만 바꾸어 주어야 하는 경우, 예를 들어

B	B	W
B	W	B
W	B	W

 

-> 이런 식으로, 시작값이 B여서 8개를 변경해야 하지만, 실제로 시작점인 B만 바꾸면 되는 경우가 생길 수 있다.

-> 이 경우 (최대 바꾸는 수인 9개에서 변경 개수를 뺀 것, 변경 개수) 중 작은 것을 return하면 된다.

 6. 8x8의 크기이므로 64 / 64-cnt 중 작은 값을 가져오면 될 것이다.

 7. 최소의 답을 구하면 된다. 

 8. 설명을 상세히 적었지만, 실제로는 매우 간단한 풀이이기 때문에 코드를 보면 이해할 수 있다.

코드