이 문제는 분무기의 영향을 받는 단위구역들의 홀짝 관계를 이용해 해결이 가능하다.

위의 그림에서 1번 위치를 중심으로 하는 십자가, 즉 노란 구역들의 수확량 합 를 생각하여 보자.

2, 3, 4, 5, 6번 위치에 분무기를 놓는다면 그것이 비료액 분무기이든 제초제 분무기이든 는 짝수(2, -2, 8, -8)만큼 바뀌게 된다.

즉, 가 홀수였다면 그대로 홀수, 짝수였다면 그대로 짝수로 유지된다는 의미이다.

단 한 곳, 1번 위치에 분무기를 놓을 때에만 가 15 또는 –15가 변해 홀짝이 바뀐다는 것을 알 수 있다.

즉 어떠한 I행 J열에 분무기가 있는지 없는지를 입력받은 농장의 최종 상태 에서 I행 J열을 중심으로 하는 십자가 구역 수확량 합의 홀짝을 확인하여 확정할 수 있다. 분무기가 설치되지 않았을 때와 홀짝이 동일하면 분무기가 없고, 그렇지 않다면 분무기가 있는 것이다.

위의 방법을 통해 분무기가 있는 위치를 모두 확정할 수 있다. 단, 분무기가 비료액을 사용할지 제초제를 사용할지에 대한 정보를 알 수 없는데 이 또한 쉽게 해결 가능하다. 위에서 구한 모든 위치에 대해 제초제를 사용하였다고 가정한 가상의 농장 의 수확량 정보를 만들자. 그리고 그 중 몇 군데를 골라 제초제를 비료액으로 교체한 것이 최종 상태 라고 생각해 보자. 의 I행 J열이 제초제에서 비료액으로 교체될 때 I행 J열을 중심으로 하는 십자가 구역들은 수확량이 2씩 늘어나는 것과 같다. 즉, 마찬가지 원리로 I행 J열에 비료액을 놓을 때에만 4로 나눈 나머지가 변화하게 된다. 따라서 농장 에 대해 수확량을 4로 나눈 나머지가 최종 상태 와 다른 구역의 제초제를 비료액으로 바꾸어 주면 된다.

각 행과 열의 합을 미리 구해 놓음으로써 이를 , 상수 시간에 구할 수 있다. 다양한 커팅 방법을 이용하여 백트래킹으로도 제한시간 안에 정답을 구할 수 있다.

koi_spray 대회 풀이