동전 뒤집기
시간 제한6초메모리 제한128 MB
N×20 이하의 N×N 격자에서 앞뒤(H/T) 동전을 행 또는 열 단위로 뒤집어 뒷면(T) 개수를 최소로 만드는 문제입니다.
문제
N^2개의 동전이 N행 N열로 탁자 위에 놓여 있다. 각 동전은 앞면 H 또는 뒷면 T가 위를 향한다. 아래 그림은 N = 3인 경우의 한 상태를 보여준다.
<그림 1>
한 번의 작업으로 임의의 한 행 또는 한 열에 있는 N개의 동전을 모두 뒤집을 수 있다. 예를 들어 그림 1의 상태에서 첫 번째 열을 모두 뒤집으면 그림 2가 되고, 이어서 첫 번째 행을 모두 뒤집으면 그림 3이 된다.
 |  |
| <그림 2> | <그림 3> |
그림 3에서는 뒷면이 위를 향한 동전이 2개이다. 그림 1의 상태에서 행이나 열 전체를 뒤집는 작업을 아무리 반복해도 뒷면 동전의 개수를 2개보다 작게 만들 수 없다.
초기 상태가 주어졌을 때, 행 또는 열 전체를 뒤집는 작업을 원하는 만큼 수행하여 만들 수 있는 뒷면 동전 개수의 최솟값을 구하라.
입력
첫째 줄에 자연수 N이 주어진다. N은 20 이하이다.
둘째 줄부터 N개의 줄에 걸쳐 각 행의 동전 상태가 주어진다. 각 줄은 길이 N의 문자열이며, 왼쪽부터 차례대로 앞면은 H, 뒷면은 T로 표시한다. 문자 사이에 공백은 없다.
출력
행 또는 열 전체를 뒤집는 작업을 수행한 뒤 만들 수 있는 뒷면 동전 개수의 최솟값을 출력한다.