레이팅 미적용농부 존은 밤중에 농장에 찾아와 소를 넘어뜨리고 가는 심심한 십 대들 때문에 가끔 골치를 앓는다. 어느 날 아침, 그는 또 그 일이 벌어졌음을 알게 된다. 그의 소 \(N^2\)마리는 밤이 시작될 때 완벽한 \(N \times N\) 정사각 격자 배열(\(1 \leq N \leq 10\))로 풀을 뜯고 있었는데, 지금은 그중 일부가 넘어져 있는 것이다.
다행히 농부 존은 트랙터와 지게차의 부품으로 소 무리를 한 번에 뒤집을 수 있는 근사한 기계, 소-일으키기 3000(Cow-Untipperator 3000)을 만들어 두었다. 덕분에 소들을 최대한 빨리 다시 일으켜 세울 수 있다. 그는 이 기계를 소 격자의 임의의 "왼쪽 위 직사각형", 즉 왼쪽 위 소를 포함하는 직사각형 부분 격자에 적용할 수 있다. 기계를 적용하면 그 직사각형 안의 모든 소가 뒤집혀서, 넘어진 소는 다시 일어서지만 안타깝게도 이미 서 있던 소는 넘어지고 만다! 다시 말해, 기계는 직사각형 안의 각 소의 상태를 "토글"한다.
농부 존은 적절한 직사각형들에 기계를 충분히 여러 번 적용하면 결국 모든 소를 원래의 서 있는 상태로 되돌릴 수 있다고 생각한다. 이를 위해 필요한 기계 적용 횟수의 최솟값을 구해 존을 도와주자.
같은 직사각형에 기계를 두 번 적용하는 것은 그 직사각형 안의 소들에게 아무런 순효과가 없으므로 무의미하다는 점에 유의한다. 따라서 각 왼쪽 위 직사각형에는 기계를 많아야 한 번만 적용하는 경우만 고려하면 된다.
문제 출제: 네이선 핀스커(Nathan Pinsker)
문제 출제: 네이선 핀스커(Nathan Pinsker)
입력의 첫째 줄에 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 각각 \(N\)개의 문자로 이루어진 문자열이 주어지며, 각 문자는 0(서 있는 소) 또는 1(넘어진 소)이다.
모든 소를 다시 일으켜 세우기 위해 농부 존이 소-일으키기 3000을 적용해야 하는 최소 횟수를 출력한다.
cowtip.in · 출력을 쓸 파일 cowtip.out3
001
111
1112In this example, if FJ applies his machine to the entire herd of cows (which is
a valid upper-left rectangle), he will
toggle their state to the following:
110
000
000
All that remains is to apply the machine to the upper-left rectangle containing
the two 1s, and he is finished. In total, this is just 2 applications.
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > January > Bronze