[🥇1 / 백준 1285 / 파이썬] 동전 뒤집기

 

1285번: 동전 뒤집기

 

문제

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

<그림 1>

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

 

<그림 2>	<그림 3>

 

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

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

입력

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

 

예제 입력 3 HHT THH THT

예제 입력 2

 

풀이

 

뒤집기를 행, 열 기준으로 무제한 수행했을 때 나올 수 있는 T의 개수를 최소 개수를 구하는 문제이다.

크게 마땅한 방법이 없어 브루트 포스로 모든 경우를 탐색해야한다.

 

행과 열 둘 중 기준을 하나 잡아야 하는데, 필자는 행으로 정하도록 하겠다.

행을 뒤집는 모든 경우의 수를 구한 뒤, 열을 차례대로 순회하며 뒤집었을 때 이득인 경우만 뒤집는다.

여기서 행을 뒤집는 연산을 최소화하기 위해 비트마스킹이 필요하다.

 

n이 3인 예제를 살펴보도록 하자.

각각의 행을 뒤집는 경우를 이진수로 살펴보자면

 

000, 001, 010, 011, 100, 101, 110, 111

 

총 8가지, 즉 2^n 가지가 존재한다.

반복문을 통해 현재 행의 비트가 1로 되어있으면 뒤집고, 아니면 가만히 둔다.

행을 뒤집는 것이 완료되었다면, 열을 기준으로 한 번 순회하며 살펴야 한다.

뒤집었을 때 T가 감소하면 뒤집은 뒤 세고, 아니면 뒤집지 않고 그냥 세준다.

 

이렇게 각 경우의 수마다 T의 최소 개수를 센 뒤 출력하면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
board = [list(input().rstrip()) for _ in range(n)]
# 실제로 행을 뒤집진 않고 행을 뒤집은 경우를 미리 만들어주고 복사만 할 것이다.
rev_board = [k[:] for k in board] 
ans = n**2

for i in range(n):
    for j in range(n):
        if rev_board[i][j] == 'T':
            rev_board[i][j] = 'H'
        else:
            rev_board[i][j] = 'T'
                    
for b in range(1<<n):
    tmp_board = []
    for i in range(n):
        if b & (1<<i):
            tmp_board.append(rev_board[i][:])
        else:
            tmp_board.append(board[i][:])
    
    cnt = 0
    for i in range(n):
        tmp = 0
        for j in range(n):
            if tmp_board[j][i] == 'T':
                tmp+=1
        cnt += min(tmp,n-tmp)
    ans = min(ans,cnt)
print(ans)