[백준] 1285 - 동전 뒤집기

 

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

1285번: 동전 뒤집기

 

풀이가 떠오르지 않아 다른 블로그를 참고하였던 문제이다.

 

핵심은 독립 시행이다.

바로 행을 뒤집는 것과 열을 뒤집는 것이 서로 영향을 끼치지 않기 때문이다.

 

주어진 제한은 1 <= N <= 20 이므로 모든 열 또는 행에 대해서 최대 2 ^ 20 만큼의 계산으로 경우를 구할 수 있다(뒤집거나 안 뒤집거나).

만약 행에 대해서 모든 경우를 구하였다면, 각 경우마다 열을 살펴보기만 하면 최솟값을 구할 수 있다.

 

즉, O(N^2 * 2^N) = 약 3억으로 6초의 시간제한을 가뿐하게 통과할 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<char>> a(20, vector<char>(20));

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 1000000000;
	for (int i = 0; i < (1 << n); i++) { //행에 대해 모든 경우의 수를 탐색
		vector<vector<char>> t = a;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				for (int k = 0; k < n; k++) {
					if (t[j][k] == 'H')t[j][k] = 'T'; //임시 배열에 행을 뒤집어준다.
					else t[j][k] = 'H';
				}
			}
		}
		int tot = 0;
		for (int i1 = 0; i1 < n; i1++) {
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (t[j][i1] == 'T')cnt++; //열을 탐색하며 뒤집었을 경우 H가 되는 개수를 센다.
			}
			if (cnt > n - cnt) {
				tot += n - cnt;
			}
			else tot += cnt;
		}
		ans = min(ans, tot);
	}
	cout << ans;
}

 

Reference

https://velog.io/@lacram/C-%EB%B0%B1%EC%A4%80-1285%EB%B2%88-%EB%8F%99%EC%A0%84-%EB%92%A4%EC%A7%91%EA%B8%B0