시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 422 | 187 | 148 | 53.818% |
영식이는 밑에 슈퍼에 가서 매일매일 시도때도 없이 과자를 사먹는다. 그러다보니 자연스럽게 동전이 많아졌다. 민식이가 놀아주지않아서 자연스럽게 왕따가된 영식이는 동전들을 N×M모양으로 배열하고 뒤집는 놀이를 하려고 한다. N과 M은 모두 홀수이다.
편의상 동전의 앞면을 0, 뒷면을 1이라고 한다.
한번 뒤집기를 할 때, 영식이는 어떤 열과 행 중에 하나를 고를 수 있다. 그리고나서 뒤집는 행동을 할 때는, 고른 열이나 행에 있는 모든 동전을 뒤집어야 한다. 0은 1이 되고 1은 0이 된다는 소리다.
영식이는 동전을 열심히 뒤집어서 각 열과 행에있는 1의 개수를 모두 짝수개로 맞추려고 한다.
영식이가 동전을 뒤집어야하는 횟수의 최솟값을 출력하는 프로그램을 작성하시오.
첫째 줄에 영식이가 동전을 놓은 세로 크기 N과 가로크기 M이 주어진다. N과 M은 1,000보다 작거나 같은 홀수이다. 둘째 줄부터 총 N개의 줄에 영식이가 각각의 줄에 M개의 동전을 놓은 방법이 주어진다.
첫째 줄에 각각의 열과 행에 동전 뒷면의 개수를 모두 짝수로 만들려고 할 때 해야하는 행동의 최솟값을 출력한다. 만약 각각의 열과 행의 동전 뒷면의 개수를 모두 짝수로 만들 수 없다면 -1을 출력한다.
3 3 111 011 001
2
5 3 111 111 111 111 111
3
3 5 00000 00000 00000
0
5 5 10101 01010 10101 01010 10101
5
예제 1의 경우 가운데 행을 뒤집고, 가운데 열을 뒤집으면 된다.