2/16기록 - 백준 1018

체스판 문제 시리즈로 백준 1018문제를 이어서 포스팅 해보려 한다. 

 

솔직히 엄청 쉬울 줄 알았는데, 이전 1100번 문제는 8*8 배열만으로 해결이 되는 문제였던 반면, 이 문제는 입력 사이즈의 배열에서 8*8배열을 만들고 그 안에서 잘못 놓여진 문자의 최소 개수를 찾아내어야 해서 제법 까다로웠다. 

 

일단 경우의 수를 생각할 수 있어야 하는데, 10*10 의 경우를 생각해 보자, 여기서 생길 수 있는 8*8 정사각형 개수를 세어보면 9가지가 나오는 것을 알 수 있다. 9*9는 4가지가 나온다. 이를 토대로 공식을 세워 볼 수 있는데, 입력할 수를 N, M이라고 했을 때, 총 (N-7) * (M-7)의 경우의 수가 나오는 것을 알 수 있다. B와 W가 1100번 문제와는 다르게 지정된 값이 없으므로 교차될 경우를 고려 하여 총 경우의 수는 2 * (N-7) * (M-7)이 된다.

 

잘라진 배열 안에서 개수를 카운트 하는 함수를 하나 만들어서 해결하려고 했다. 함수는 잘라진 배열 x~x+8, y~y+8범위 안에서 올바른 색이 아닐 경우 count 해주고, count = Math.min(count, 64 - count); 의 형태로 count의 최솟값을 구하기 위해 전체 개수 64에서 빼준 값과 비교해 주어야 한다.(색이 반대일 경우도 생각해 주어야 하므로)

 

코드를 보면서 이해해 보자. 먼저 작동하는 건 boolean 배열을 만들고 charAt()으로 W의 경우 true, 아닐 경우 false를 반환하게 만들어주었다. 그리고 위에서 설명했던 경우의 수만큼 이중 for문을 만들어 counting 함수를 호출해서 문제를 해결할 수 있었다. 

 

함수는 boolean 타입의 check변수를 매개변수를 x,y로 가진 배열 arr로 선언하고, 이를 기존 arr배열과 비교하여 올바른 색이 아니라면 count++ 시켜주었다.

이 문제의 핵심의 check = !check부분이라고 할 수 있는데, 다음 칸은 색이 바뀌므로 true라면 false로, false라면 true로 변경시켜 주어야한다.

마지막으로 count부분에서 최솟값을 구해야하므로, 색이 변경되는 것을 고려하여 count와 (전체-count)를 비교해서 count값을 도출해 주고, static 정적 변수로 선언해 준 MAX값을 가진 answer변수와 비교하여 최종 최솟값을 구해낼 수 있도록 만들어 주었다.

 

이정도만 되어도 꽤 어려운 것 같은데, 다 풀고 나서 보니 문제 난이도가 쉬운거라는 포스팅들이 많았다... ㅠㅠㅠㅠ 갈길이 멀다 ㅠㅠㅠㅠ

 

2/16 기록 끝!!!!!!!!