[Baekjoon-Python] 1285 : 동전 뒤집기

https://www.acmicpc.net/problem/1285

접근

비트마스크를 적용하기 위해 H = 0, T = 1 이진수로 치환한다.
행 방향으로 뒤집을 수 있는 모든 경우의 수를 구한다.
열 방향으로 탐색하면서 T 개수가 많으면 뒤집는다.

풀이

from sys import stdin


N = int(stdin.readline())
coins = []
reverse_coins = []
for _ in range(N):
    i = N - 1
    bit = 0
    for state in stdin.readline().rstrip():
        if state == "T": # (1)
            bit += 1 << i
        i -= 1
    coins.append(bit)
    reverse_coins.append(~bit) # (2)

ans = N**2
for bit in range(1 << N): # (3)
    tmp_coins = []
    for i in range(N): # (4)
        if 1 << i & bit:
            tmp_coins.append(coins[i])
        else:
            tmp_coins.append(reverse_coins[i])

    total_t_cnt = 0
    for i in range(N):
        t_cnt = 0
        for coin in tmp_coins: # (5)
            if 1 << i & coin:
                t_cnt += 1
        total_t_cnt += min(t_cnt, N - t_cnt) # (6)
    ans = min(ans, total_t_cnt)

print(ans)