N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.
이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.
<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.
N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.
출력
첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.
입력 예시
3
HHT
THH
THT
출력 예시
2
풀이
먼저, 행을 뒤집는 일은 브루트포스로 쉽게 해 볼 수 있을 것 같다. 비트마스킹을 활용하면 O(1) 시간 내로 연산을 마칠 수 있다. 모든 행의 비트값의 합은 2^N-1이므로, (2^N-1)-(현재 행의 비트값)으로 갱신이 가능하다.
열 역시 똑같이 브루트포스로 뒤집게 되면 총 O(2^(2N))의 시간복잡도를 가지게 된다. N이 최대 20이므로 이는 분명히 시간 초과를 야기한다. 여기서 우리는 다른 사실을 관찰할 수 있는데, 행이 고정된 상태이므로 열을 뒤집거나, 뒤집지 않거나를 그리디하게 결정할 수 있다는 사실이다. i번째 열에 T개의 뒷면이 있다면, 우리는 min(T, N-T)값을 취사선택하여 최적의 T를 구할 수 있다.
즉 그리디 + 비트마스킹 + 브루트포스로 풀이해볼 수 있겠으며, 총 시간복잡도는 O(N^2 * 2^N)이 된다.
풀이 코드
N = int(input())
rows = [0]*N
for i in range(N) :
coins = input().strip()
for j in range(N) :
if coins[j] == 'T' :
rows[i] += (1 << j)
def masking(row) :
for i in range(N) :
if row & (1 << i) :
rows[i] = (1 << N) - rows[i] - 1
def cal_value(row) :
value = 0
masking(row)
for i in range(N) :
cols = 0
for j in range(N) :
if rows[j] & (1 << i) :
cols += 1
value += min(cols, N-cols)
masking(row)
return value
ans = N**2
for i in range(1 << N) :
ans = min(ans, cal_value(i))
print(ans)
