동전 뒤집기 2

N^2개의 동전이 N행 N열로 탁자 위에 놓여 있다. 각 동전은 앞면(H) 또는 뒷면(T)이 위를 향한다. 다음 그림은 N = 3인 경우의 예이다.

<그림 1>

한 번의 작업으로 임의의 한 행 또는 한 열을 골라, 그 안에 있는 N개의 동전을 모두 뒤집을 수 있다. 예를 들어 그림 1의 상태에서 첫 번째 열의 동전을 모두 뒤집으면 그림 2가 되고, 이어서 그림 2의 상태에서 첫 번째 행의 동전을 모두 뒤집으면 그림 3이 된다.

<그림 2>	<그림 3>

그림 3에서는 뒷면이 위를 향한 동전이 두 개이다. 그림 1의 상태에서 허용된 작업을 아무리 반복해도 뒷면이 위를 향한 동전 수를 두 개보다 작게 만들 수는 없다.

동전들의 초기 상태가 주어질 때, 행 또는 열 전체를 뒤집는 작업을 원하는 만큼 수행한 뒤 뒷면이 위를 향한 동전 개수의 최솟값을 구하시오.

첫째 줄에 32 이하의 자연수 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 길이 N인 문자열이 주어진다. 각 문자열은 한 행에 놓인 동전의 상태를 왼쪽부터 차례대로 나타낸다. 앞면이 위를 향하면 H, 뒷면이 위를 향하면 T로 표시하며, 한 줄 안에는 공백이 없다.

한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 원하는 만큼 수행했을 때, 뒷면이 위를 향한 동전 개수의 최솟값을 출력한다.