문제
N^2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.
<그림 1>
이들 N^2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.
| <그림 2> | <그림 3> |
|---|---|
 |  |
<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.
N^2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.
출력
첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.
풀이
이 문제의 포인트는 행과 열을 동시에 모두 고민하려고 하지 않는 것이다. 모든 행에 대해 뒤집을지 말지를 먼저 전부 선택하고 나면, 그 뒤에는 열에 대해서는 따로 완전탐색할 필요가 없다.
이유는 행 상태가 하나 정해졌을 때 각 열은 독립적으로 최적 선택이 가능하기 때문이다. 어떤 열에서 뒷면의 개수가 tail개라면, 그 열을 뒤집지 않는 경우와 뒤집는 경우 중 더 작은 값인 min(tail, N - tail)만 취하면 된다. 즉 완전탐색의 대상은 행 선택뿐이고, 열은 그 결과를 바로 계산할 수 있다.
그래서 경우의 수는 2^N개다. 여기서 N <= 20이라는 제한이 결정적이다. 2^20 정도면 모든 행 뒤집기 경우를 확인해도 충분한 시간 안에 처리할 수 있으므로, 이 완전탐색이 성립한다는 점을 알아차리는 것이 핵심이었다.
코드에서는 각 행을 비트마스크로 표현해 T 위치를 저장하고, 재귀로 각 행을 뒤집을지 말지를 모두 탐색한다. 행 선택이 하나 정해질 때마다 각 열의 최소 뒷면 개수를 계산해 전체 답을 갱신한다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, ans = Integer.MAX_VALUE;
static int[] coins;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
coins = new int[N];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < N; j++) {
if (input.charAt(j) == 'T')
coins[i] |= (1 << j);
}
}
solve(0);
System.out.println(ans);
}
static void solve(int cnt) {
if (cnt == N) {
int sum = 0;
for (int i = 1; i < (1 << N); i *= 2) {
int tail = 0;
for (int j = 0; j < N; j++)
if ((coins[j] & i) != 0)
tail++;
sum += Math.min(tail, N - tail);
}
ans = Math.min(ans, sum);
return;
}
// 동전 뒤집기
coins[cnt] = ~coins[cnt];
solve(cnt + 1);
// 동전 안뒤집기
coins[cnt] = ~coins[cnt];
solve(cnt + 1);
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
행과 열을 동시에 고민하면 복잡하지만, 행을 먼저 고정하면 열은 자동으로 최적 선택이 된다. 이 관점 때문에 완전탐색 범위가 2^N으로 줄어드는 문제다.
