[백준 1285번] 동전 뒤집기 (Python3)

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는 신이야