백준 1285 파이썬 - 동전 뒤집기

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

1285번: 동전 뒤집기

문제

N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.

<그림 1>

이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.

<그림 2>

<그림 3>

<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.

N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

코드

import sys
n = int(sys.stdin.readline())
board = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
def change(x):
    return 'T' if x == 'H' else 'H'
ans = n * n
for bit in range(1 << n):
    sum = 0
    for i in range(n):
        tail = 0
        for j in range(n):
            cur = board[j][i]
            if (bit & (1 << j)) != 0:
                cur = change(cur)
            if cur == 'T':
                tail += 1
        sum += min(tail, n - tail)
    if sum < ans:
        ans = sum
sys.stdout.write(str(ans))

풀이

비트마스크를 통해 푼다. 행을 뒤집을 수 있는 경우를 2의 N가지 비트마스크를 통해 표현한다. 뒤집거나 안뒤집거나의 두 가지 경우만 있기 때문에 이것이 가능하다. 0 부터 n - 1자리 수까지 숫자가 있고 k자리 수가 1이라는 것은 k번째 행을 뒤집는 것을 의미한다. 모든 경우에 대해 반복문을 돌리고, 이중 for문으로 뒤집을지를 결정한다. 열에 대해 뒤집을지 안뒤집을지도 결정해준다. 열의 경우 현재 T와 H중 최소값을 sum에 더해주면 된다. 모든 경우마다 답을 구해 최솟값을 출력하면 된다.