[Baekjoon] 동전 뒤집기

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

1285번: 동전 뒤집기

 

---

 

문제 해결 과정

착안

$N^2$ 개의 동전의 초기 상태로부터 뒷면(T)인 동전의 갯수가 최소가 되도록 행 또는 열을 뒤집는 경우를 찾기 위해서는 가능한 모든 경우를 확인해보아야 한다. 이때, 행이나 열을 뒤집는 동작을 수행할 때 선택된 행과 열 중에서 어느 것을 먼저 뒤집더라도 결과가 동일하므로, 편의상 항상 행을 먼저 다 뒤집은 다음에 열을 뒤집는 경우만 살펴볼 수 있다.

 

행 또는 열을 뒤집는 모든 경우의 수는 각각의 행과 열을 뒤집거나 뒤집지 않는 2 가지의 경우가 있으므로,

$$2^N \times 2^N = 2^{2N}$$

이다.

 

그러나, 문제에서 요구하는 것은 뒷면의 갯수가 최소가 되도록 하는 경우를 찾는 것이므로 실제로는 위와 같은 경우의 수를 모두 살펴볼 필요는 없다. 왜냐하면 뒤집을 행을 선택하여 모두 뒤집은 상황에서는, 특정 열을 뒤집었을 때 뒷면의 갯수가 이전보다 줄어드는 열만 선택하여 뒤집으면 뒷면의 갯수가 최소가 될 가능성이 있는 경우만 살펴보는 것이기 때문이다. 즉, 행을 선택하여 먼저 다 뒤집고 난 상태에서($2^N$ 가지의 경우), 뒷면의 갯수를 최대한 줄이도록 열을 뒤집는 방법의 수는 각각에 대해 1 가지 방법 밖에 없으므로 실제로는 $2^N$ 가지 경우만 살펴보면 되는 것이다.

 

따라서, 이 문제는 실질적으로 뒤집을 행을 선택하는 $2^N$ 가지의 경우를 살펴본 다음, 각각의 경우에 대해 뒷면의 갯수를 최대한 줄이는 방법 (각 경우에 대해 1 가지 방법만 존재)으로 열을 뒤집고 나서 뒷면의 갯수를 세어보는 문제가 된다.

 

구현

한 줄에 $N$ 개로 주어지는 동전의 앞, 뒷면을 각각의 한 줄씩 $N$ 개의 비트 형태로 표현(비트마스킹, bitmasking)하면 각각의 행을 하나의 숫자만으로 표현이 가능하며, 비트 NOT 연산자(~)를 사용해 행을 뒤집는 연산이 매우 간단해져 효율적인 문제 해결이 가능하다.

 

행을 뒤집는 경우는 $2^N$ 가지의 모든 경우를 전부 살펴보아야하므로 재귀 함수의 형태로 구현하였고, 각각의 열은 직접 뒤집을 필요 없이 $i \space (1 \le i \le N) $ 번째 열의 동전의 뒷면의 갯수 $T_i$ (뒤집지 않는 경우)를 계산해 $N - T_i$ (뒤집는 경우)와 비교하여 더 작은 값을 누적하여 합하는 방식으로 전체 동전의 뒷면의 갯수를 구해 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

int N;
int Min = 400;

int CountColumn(vector<int> rows, int col)
{
	int count = 0;
	for (int i = 0; i < N; i++)
		if (rows[i] >> col & 1)
			count++;

	if (count > N / 2)
		count = N - count;

	return count;
}

void FlipRow(vector<int> rows, int row)
{
	if (row < N)
	{
		FlipRow(rows, row + 1);
		rows[row] = ~rows[row];
		FlipRow(rows, row + 1);
	}

	int count = 0;
	for (int i = 0; i < N; i++)
		count += CountColumn(rows, i);

	if (Min > count)
		Min = count;
}

int main()
{
	cin >> N;
	vector<int> Rows(N);
	string str;
	for (int i = 0; i < N; i++)
	{
		cin >> str;
		int one = 1;
		for (char c : str)
		{
			if (c == 'T')
				Rows[i] += one;
			one <<= 1;
		}
	}

	FlipRow(Rows, 0);
	cout << Min << "\n";
	return 0;
}

 

실행 결과