반전 정리 timer 20s memory 1024MB

2년 전 IO 홍보물을 인쇄할 때 겪은 문제 이후, 컨퍼런스의 마케팅 팀은 인터랙티브 설치물을 사용하기로 했다. 이 설치물은 2\mathbf{N}행 2\mathbf{N}열의 터치스크린 행렬로 이루어져 있다. 각 터치스크린은 대문자 I 또는 대문자 O 중 하나를 표시할 수 있다. 어떤 스크린을 터치하면, 터치 직전에 표시하고 있지 않던 글자로 표시가 바뀐다(즉, I와 O가 서로 전환된다).

당신은 이 설치물 중 하나를 보고 있는데, 너무 정돈되지 않았다고 느꼈다. 당신은 몇몇 글자를 바꿔서 위쪽 \mathbf{N}개 행에 표시된 I의 개수 합이 아래쪽 \mathbf{N}개 행의 I 개수 합과 같아지게 하고 싶다. 동시에, 가장 왼쪽 \mathbf{N}개 열에 표시된 I의 개수 합이 가장 오른쪽 \mathbf{N}개 열의 I 개수 합과 같아지게 하고 싶다.

예를 들어 위의 왼쪽 그림에서 \mathbf{N}=2이다. 위쪽 2개 행에는 I가 총 3개 표시되어 있고, 아래쪽 2개 행에는 5개가 표시되어 있다. 반면 가장 왼쪽 2개 열과 가장 오른쪽 2개 열에는 모두 I가 총 4개씩 표시되어 있다. 강조 표시된 두 스크린을 터치하면, 오른쪽 그림과 같은 상태로 바꿀 수 있다. 이 상태에서는 위쪽 2개 행과 아래쪽 2개 행 모두 I가 4개씩이 되고, 왼쪽/오른쪽도 여전히 균형을 유지한다.

설치물의 현재 상태가 주어질 때, 위 조건을 모두 만족하기 위해 필요한 최소 터치 횟수를 구하라.