import sys
input = sys.stdin.readline
def turn(n):
for i in range(N):
board[i][n] = abs(board[i][n]-1)
N = int(input())
board = []
for i in range(N):
board.append([*map(lambda x:1 if x=="T" else 0,input().strip())])
result = N**2
bitlast = 0
for bit in range(1<<N):
for n in range(N):
if (bit^bitlast)&(1<<n):
turn(n)
result = min(result,sum(map(lambda x:min(sum(x),N-sum(x)),board)))
bitlast = bit
print(result)
불 끄기 [백준 14939번] 불 끄기 (Python3) (tistory.com) 문제와 비슷한 방식으로 풀 수 있는 문제이다.
비트마스킹을 이용한 브루트 포스로 풀 수 있다.
열을 기준으로 모든 경우의 수에 대해 동전을 뒤집어 보고, 행은 남아있는 동전이 앞면이 많으면 뒤집고, 앞면이 적으면 뒤집지 않는 방식으로 최솟값을 구할 수 있다.
참고로 파이썬으로 제출하면 억까를 당할 수 있으니 pypy3로 제출하는걸 추천한다.
오늘의 교훈) pypy는 신이야