체스판은 행을 기준으로 2개의 패턴(WBWBWBWB or BWBWBWBW)밖에 존재하기 않기 때문에

이것과 입력을 비교하는 방식으로 코드를 짰습니다.

입력의 각 행을 8개씩 잘라서 이것이 위의 두 패턴과 다른 갯수를 계산한 뒤

계산된 각각의 결과를 열 방향으로 8개씩 더해서 모든 경우에 대한 최종적으로 고쳐야하는 갯수를 계산했고

이 값 중에 가장 작은 값을 출력했습니다.

주어진 입력에 대해서는 당연히 옳은 결과가 나왔고,

이외에 시간날 때마다 생각하는 모든 경우를 다 넣어봐도 정답이 출력됐습니다.

그런데 제출하면 계속 틀렸다고 나오네요...

반례가 있다는 얘기인데 도저히 반례를 찾을 수 없습니다.

혹시 반례를 찾아주실 수 있을까요...?

결국 테스트 코드 짜서 반례 찾았습니다.

인터넷에 있는 정답이랑 제 코드랑 비교해서

값이 다르게 나올 때의 입력값을 찾아봤는데 다음과 같은 경우에서 결과가 다르게 나오네요.

N, M = 10, 8

board :

WBWWBBBW
BWBBWWWW
BWWWBBBW
BWWWWWWW
BWBBWBWB
BWWBBBWW
WBWBWBBW
BWBWBWWW
WBWWBBWW
WBWWWBBW

답이 26이 나와야 하는데 제 코드는 25가 나오네요.

sglim9607   2년 전

위에 글에 예시의 정답 26이아니라 25가 맞습니다. 

댓글을 작성하려면 로그인해야 합니다.